Vertex Coloring by Multistage Branch and Bound

Massimiliano Caramia, Paolo Dell'Olmo

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002


In this paper we design an algorithm based on branch and bound rules embedded in a multistage scheme which allows iterative visits of subgraphs. The algorithm is conceived to finding lower bounds of the chromatic number of graphs, and, by means of simple coloring extension rules, it is often capable of finding optimal solutions. Computational results on benchmarks are provided.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Start Conference Manager
Conference Systems