Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
Año:2015
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
In this paper a fast greedy sequential heuristic for the vertex colouring problem is presented. The suggested algorithm builds the same colouring of the graph as the well-known greedy sequential heuristic in which on every step the current vertex is coloured in the minimum possible colour. Our main contributions include introduction of a special matrix of forbidden colours and application of efficient bitwise operations on bit representations of the adjacency and forbidden colours matrices. Computational experiments show that in comparison with the classical greedy heuristic the average speedup of the developed approach is 2.6 times on DIMACS instances.
Internacional
Si
JCR del ISI
Si
Título de la revista
Journal of Combinatorial Optimization
ISSN
1382-6905
Factor de impacto JCR
1,043
Información de impacto
Q2, Datos JCR del año 2013
Volumen
DOI
10.1007/s10878-015-9862-1
Número de revista
31
Desde la página
1665
Hasta la página
1677
Mes
MARZO
Ranking
Q2, Area: MATHEMATICS APPLIED (81/254) (datos 2015)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Larisa Komosko
  • Autor: Mikhail Batsyn
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Panos Pardalos (Universidad de Florida)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Centro o Instituto I+D+i: Centro de Automática y Robótica (CAR). Centro Mixto UPM-CSIC
  • Departamento: Ingeniería Eléctrica, Electrónica Automática y Física Aplicada
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)