A column generation approach for graph coloring

A column generation approach for graph coloring

0.00 Avg rating0 Votes
Article ID: iaor19972125
Country: United States
Volume: 8
Issue: 4
Start Page Number: 344
End Page Number: 354
Publication Date: Oct 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: graph colouring
Abstract:

The authors present a method for solving the independent set formulation of the graph coloring problem (where there is one variable for each independent set in the graph). They use a column generation method for implicit optimization of the linear program at each node of the branch-and-bound tree. This approach, while requiring the solution of a difficult subproblem as well as needing sophisticated branching rules, solves small to moderate size problems quickly. The authors have also implemented an exact graph coloring algorithm based on DSATUR for comparison. Implementation details and computational experience are presented.

Reviews

Required fields are marked *. Your email address will not be published.