Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Infra-chromatic bound for exact maximum clique search
Year:2015
Research Areas
  • Information technology and adata processing
Information
Abstract
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph. Li and Quan in [17] describe a way to compute even tighter bounds by reducing each colored subproblem to maximum satisfiability problem (MaxSAT). Moreover they show empirically that the new bounds obtained may be lower than the chromatic number. Based on this idea this paper shows an efficient way to compute related ?infra-chromatic? upper bounds without an explicit MaxSAT encoding. The reported results show some of the best times for a stand-alone computer over a number of instances from standard benchmarks.
International
Si
JCR
Si
Title
Computers & Operations Research
ISBN
0305-0548
Impact factor JCR
1,988
Impact info
Q1: Datos JCR 2015
Volume
10.1016/j.cor.2015.06.009
Journal number
64
From page
293
To page
303
Month
JUNIO
Ranking
Area: ENGINEERING, INDUSTRIAL (11/44 Q1) Area: OPERATIONS RESEARCH & MANAGEMENT SCIENCE (19/82 Q1)
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Aleksey Nikolaev (LATNA)
  • Autor: Mikhail Batsyn (LATNA)
Research Group, Departaments and Institutes related
  • Creador: 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)