Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
A new DSATUR-based algorithm for exact vertex coloring
Año:2012
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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.
Internacional
Si
JCR del ISI
Si
Título de la revista
Computers &OperationsResearch
ISSN
0305-0548
Factor de impacto JCR
1,909
Información de impacto
Volumen
DOI
10.1016/j.cor.2011.10.008
Número de revista
39
Desde la página
1724
Hasta la página
1733
Mes
SIN MES
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Electrónica, Automática e Informática Industrial
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)