ALCOMFT-TR-02-106

Torsten Fahle
Cost Based Filtering vs. Upper Bounds for Maximum Clique
Paderborn. Work packages 3 and 4. May 2002.

Abstract: In this paper we consider a branch-and-bound algorithm for the maximum clique problem. 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). Doing this, we can reduce the number of choice points visited by a typical factor of 10 - 50.

Additionally, we present a taxonomy of upper bounds used in the OR community 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.

Keywords: maximum clique, cost based filtering, branch-and-bound.

Postscript file: ALCOMFT-TR-02-106.ps.gz (76 kb).