Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Relaxed approximate coloring in exact maximum clique search
Year:2013
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
Si
Title
Computers & Operations Research
ISBN
0305-0548
Impact factor JCR
1,909
Impact info
Volume
44
10.1016/j.cor.2013.10.018
Journal number
From page
185
To page
192
Month
SIN MES
Ranking
Q1 (10 sobre 43 en ENGINEERING, INDUSTRIAL)
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Cristobal Tapia Garcia (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)