• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Initial Sorting of Vertices in the Maximum Clique Problem Reviewed

Lecture Notes in Computer Science. 2014. Vol. 8426. No. DOI 10.1007/978-3-319-09584-4_12. P. 111-120.
Pablo San Segundo ., Alvaro Lopez ., Mikhail Batsyn.

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].