Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Infra-chromatic bound for exact maximum clique search
Año:2015
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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.
Internacional
Si
JCR del ISI
Si
Título de la revista
Computers & Operations Research
ISSN
0305-0548
Factor de impacto JCR
1,988
Información de impacto
Q1: Datos JCR 2015
Volumen
DOI
10.1016/j.cor.2015.06.009
Número de revista
64
Desde la página
293
Hasta la página
303
Mes
JUNIO
Ranking
Area: ENGINEERING, INDUSTRIAL (11/44 Q1) Area: OPERATIONS RESEARCH & MANAGEMENT SCIENCE (19/82 Q1)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Aleksey Nikolaev (LATNA)
  • Autor: Mikhail Batsyn (LATNA)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Ingeniería Eléctrica, Electrónica Automática y Física Aplicada
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)