INVESTIGADORES
ZABALA Paula Lorena
congresos y reuniones científicas
Título:
A branch-and-cut algorithm for graph coloring
Autor/es:
MÉNDEZ-DÍAZ, ISABEL; ZABALA, PAULA
Lugar:
Ithaca
Reunión:
Simposio; Computational Symposium on Graph Coloring and its Generalizations; 2002
Institución organizadora:
Cornell University
Resumen:
We present a Branch-and-Cut algorithm for exact graph coloring problem. In a previous paper, we have investigated the facet estructure of the 0/1-polytope associated with an integer programming formulation of the graph coloring problem. In this paper we report on a Branch-and-Cut algorithm that is based on these theoretical results. Our computational experiences compare favorably with the well-known exact graph coloring algorithm DSATUR.
