Groupe d’études et de recherche en analyse des décisions


A Decomposition Algorithm for Computing Bounds on the Clique Number of a Graph

, et

We consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bound on the clique number of a graph, we present a decomposition algorithm which is guaranteed to improve upon that upper bound. Computational experiments on DIMACS instances show that, on average, this algorithm can reduce the gap between the upper bound and the clique number by about 60%. We also show how to use this decomposition algorithm to improve the computation of lower bounds on the clique number of a graph.

, 21 pages