Optimization Online


An improved DSATUR-based Branch and Bound for the Vertex Coloring Problem

Fabio Furini(fabio.furini***at***dauphine.fr)
Virginie Gabrel(virginie.gabrel***at***dauphine.fr)
Ternier Ian-Christopher(ianchristopher.ternier***at***dauphine.fr)

Abstract: Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR based Branch and Bound (DSATUR) is an effective exact algorithm for the VCP. One of its main drawback is that a lower bound is computed only once and it is never updated. We introduce a reduced graph which allows the computation of lower bounds at nodes of the branching tree. We compare the effectiveness of different classical VCP bounds, plus a new lower bound based on the 1-to-1 mapping between VCPs and Stable Set Problems. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of instances solved to proven optimality. Similar results can be achieved for a subset of high density DIMACS instances.

Keywords: Graph Coloring, DSATUR, Branch and Bound.

Category 1: Integer Programming

Category 2: Network Optimization


Download: [PDF]

Entry Submitted: 10/14/2015
Entry Accepted: 10/14/2015
Entry Last Modified: 10/14/2015

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 Optimization Society