Affiliations: [1] Center for Automation and Robotics and Polytechnic, University of Madrid, C/Jose Gutiérrez Abascal, 2, 2006 Madrid, Spain. E-mail: pablo.sansegundo@upm.es | [2] Laboratory of Algorithms and Technologies for Network Analysis, National Research University, Higher School of Economics, 136 Rodionova Street, Nizhny Novgorod, Russia | [3] Center for Applied Optimization, University of Florida, 401 Weil Hall, P.O. Box 116595, Gainesville, FL 32611-6595, USA
Correspondence:
[*]
Corresponding author.
Abstract: 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) 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.
Keywords: maximum clique, approximate-colouring, branch-and-bound, combinatorial optimization, exact search, maximum satisfiability
Journal: Informatica, vol. 27, no. 2, pp. 463-487, 2016
