A branch and bound algorithm for the maximum clique problem

We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.

---

Zusammenfassung Wir stellen einen Branch and Bound Algorithmus für das Maximum Clique Problem in einem beliebigen Graphen vor. Das Hauptaugenmerk richtet sich dabei auf die Bestimmung oberer Schranken mit Hilfe von Färbungen von Graphen. Es wird eine Modifikation einer bekannten Färbungsmethode, genannt DSATUR, verwendet, mit der sich gleichzeitig obere und untere Schranken für die Cliquezahl erstellen lassen.