Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Improved infra-chromatic bound for exact maximum clique search
Year:2016
Research Areas
  • Information technology and adata processing
Information
Abstract
This paper improves an infra-chromatic bound which is used by the exact branch-andbound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs.
International
Si
JCR
Si
Title
Informatica-Lithuan
ISBN
0868-4952
Impact factor JCR
1,386
Impact info
Q1, Datos JCR del año 2015
Volume
27
10.15388/Informatica.2016.95
Journal number
2
From page
463
To page
487
Month
ABRIL
Ranking
Area: MATHEMATICS APPLIED (47/254-Q1)
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Aleksey Nikolaev (LATNA)
  • Autor: Mikhail Batsyn (LATNA)
  • Autor: Alvaro Lopez
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Control Inteligente
  • Centro o Instituto I+D+i: Centro de Automática y Robótica (CAR). Centro Mixto UPM-CSIC
  • 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)