Back

G-2007-01

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

, , and

BibTeX reference

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

Research Axis

Publication

A sequential elimination algorithm for computing bounds on the clique number of a graph
, , and
Discrete Optimization, 615–628, 2008 BibTeX reference