Search for items in this repository.
A new DSATUR-based algorithm for exact vertex coloring
San Segundo Carrillo, Pablo
A new DSATUR-based algorithm for exact vertex coloring.
"Computers and Operations Research", v. 39
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.
Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
Check whether the spanish journal in which you have published an article allows you to also publish it under open access.