Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
Year:2015
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
Si
Title
Journal of Combinatorial Optimization
ISBN
1382-6905
Impact factor JCR
1,043
Impact info
Q2, Datos JCR del año 2013
Volume
10.1007/s10878-015-9862-1
Journal number
31
From page
1665
To page
1677
Month
MARZO
Ranking
Q2, Area: MATHEMATICS APPLIED (81/254) (datos 2015)
Participants
  • Autor: Larisa Komosko
  • Autor: Mikhail Batsyn
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Panos Pardalos (Universidad de Florida)
Research Group, Departaments and Institutes related
  • 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 2019 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)