ALCOMFT-TR-03-180

Torsten Fahle
Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique
Paderborn. Work packages 3 and 4. December 2003.

Abstract: We consider a branch-and-bound algorithm for maximum clique problems. We introduce cost based filtering techniques for the so-called candidate set (i.e. a set of nodes that can possibly extend the clique in the current choice point).

Additionally, we present a taxonomy of upper bounds for maximum clique. Analytical results show that our cost based filtering is in a sense as tight as most of these well-known bounds for the maximum clique problem.

Experiments demonstrate that the combination of cost based filtering and vertex coloring bounds outperforms the old approach as well as approaches that only apply either of these techniques. Furthermore, the new algorithm is competitive with other recent algorithms for maximum clique.

Postscript file: ALCOMFT-TR-03-180.ps.gz (86 kb).