A new DSATUR‐based algorithm for exact vertex coloring

A new DSATUR‐based algorithm for exact vertex coloring

0.00 Avg rating0 Votes
Article ID: iaor201111475
Volume: 39
Issue: 7
Start Page Number: 1724
End Page Number: 1733
Publication Date: Jul 2012
Journal: Computers and Operations Research
Authors:
Keywords: graphical methods, graph coloring
Abstract:

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.

Reviews

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