Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Relaxed approximate coloring in exact maximum clique search
Año:2013
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
This paper presents selective coloring as a new paradigm for branch-and-bound exact maximum clique search. Approximate coloring has, in recent, years been at the heart of leading solvers in the field. Selective coloring proposes to relax coloring up to a certain threshold. The result is a less informed but lighter decision heuristic. Different operators for the remaining uncolored vertices give rise to algorithmic variants integrated in a new BBMCL framework. BBMCL allows for an interesting comparison between approximate coloring and degree-based decision heuristics. The paper also reports extensive empirical tests. Selective coloring algorithms are fastest for a large subset of the graphs considered.
Internacional
Si
JCR del ISI
Si
Título de la revista
Computers & Operations Research
ISSN
0305-0548
Factor de impacto JCR
1,909
Información de impacto
Volumen
44
DOI
10.1016/j.cor.2013.10.018
Número de revista
Desde la página
185
Hasta la página
192
Mes
SIN MES
Ranking
Q1 (10 sobre 43 en ENGINEERING, INDUSTRIAL)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Cristobal Tapia Garcia (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)