A Branch-and-Cut Algorithm for Graph Coloring

Isabel Mendez Diaz and Paula Zabala

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

Abstract

We present a Branch-and-Cut algorithm for the graph coloring problem. In a previous work, we studied the facet estructure of the 0/1-polytope associated with an integer programming formulation of the graph coloring problem. Based on these theoretical results a Branch-and-Cut algorithm is developed. Our computational experiences compare favorably with the well-known exact graph coloring algorithm DSATUR.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Maintainer trick@cmu.edu.
Start Conference Manager
Conference Systems