Optimization Online


A Branch-and-Cut Algorithm for Graph Coloring

Isabel Méndez-Díaz (imendez***at***dc.uba.ar)
Paula Zabala (pzabala***at***dc.uba.ar)

Abstract: In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably with the well-known exact graph coloring algorithm DSATUR.

Keywords: Graph Coloring; Integer Programming; Branch-and-Cut algorithms

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Reporte Técnico TR 02-001 Departamento de Computación Universidad de Buenos Aires noviembre de 2002 http://www.dc.uba.ar

Download: [Compressed Postscript][PDF]

Entry Submitted: 09/02/2003
Entry Accepted: 09/02/2003
Entry Last Modified: 09/02/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society