Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
A new DSATUR-based algorithm for exact vertex coloring
Year:2012
Research Areas
  • Information technology and adata processing
Information
Abstract
This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.
International
Si
JCR
Si
Title
Computers &OperationsResearch
ISBN
0305-0548
Impact factor JCR
1,909
Impact info
Volume
10.1016/j.cor.2011.10.008
Journal number
39
From page
1724
To page
1733
Month
SIN MES
Ranking
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Electrónica, Automática e Informática Industrial
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)