Informatica Logo

INFORMATICA
International Journal

Main Page
Editorial Board
Abstracting/Indexing
Instructions to Authors
Subscription Information


Contents
Author Index
Papers in Production

INFORMATICA, 2016, Vol. 27, No. 2, 463-487
© Institute of Mathematics and Informatics,
DOI: http://dx.doi.org/10.15388/Informatica.2016.95

ISSN 0868-4952

Improved Infra-Chromatic Bound for Exact Maximum Clique Search

Pablo SAN SEGUNDO1, Alexey NIKOLAEV, Mikhail BATSYN, Panos M. PARDALOS

Center for Automation and Robotics and Polytechnic, University of Madrid C/Jose Gutiérrez Abascal, 2, 2006 Madrid, Spain Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, 136 Rodionova Street, Nizhny Novgorod, Russia Center for Applied Optimization, University of Florida 401 Weil Hall, P.O. Box 116595, Gainesville, FL 32611-6595, USA E-mail: pablo.sansegundo@upm.es

Abstract

This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX \cite{17} 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 optimiza-\break tion, exact search, maximum satisfiability


1Corresponding author.
To preview Lithuanian abstract see full article text

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


TopTop Copyright © INFORMATICA, Vilnius University Institute of Mathematics and Informatics, 2010