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

Article

Improved Infra-Chromatic Bound for Exact Maximum Clique Search

Informatica. 2016. Vol. 27. No. 2. P. 463-487.
San Segundo P., Nikolaev A., Batsyn M., Pardalos P.M.

This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX (San Segundo et al., 2015, Computers & Operations Research, p. 293-303) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of color subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-coloring 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.