Observatorio de I+D+i UPM

Memorias de investigación
Communications at congresses:
Initial sorting of vertices in the maximum clique problem reviewed
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
In recent years there have been a number of important improvements in exact color-based maximum clique solvers, which have considerably enhanced their performance. Initial vertex ordering is one strategy known to have a significant impact on the size of the search tree. Typically, a degenerate sorting by minimum degree is used; literature also reports different tiebreaking strategies. A systematic study of the impact of initial sorting in the light of new cutting-edge ideas (e.g. recoloring [8], selective coloring [13], ILS initial lower bound computation [15-16] or MaxSAT-based pruning [14]) is, however, lacking. This paper presents a new initial sorting procedure and relates performance to the new mentioned variants implemented in leading solver BBMC [9-10].
International
Si
Congress
IX Conf. on Learning and Intelligent Optimization (LION 8) http://caopt.com/LION8/
960
Place
Florida, USA, 2014
Reviewers
Si
ISBN/ISSN
978-3-319-09584-4
10.1007/978-3-319-09584-4_12
Start Date
16/02/2014
End Date
21/02/2014
From page
111
To page
120
Learning and Intelligent Optimization LNCS 8426
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
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)