org.jgrapht.alg.color

Class SaturationDegreeColoring<V,E>

java.lang.Object

org.jgrapht.alg.color.SaturationDegreeColoring<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexColoringAlgorithm<V>

public class SaturationDegreeColoring<V,E>
extends Object
implements VertexColoringAlgorithm<V>

The Dsatur greedy coloring algorithm.

This is the greedy coloring algorithm using saturation degree ordering. The saturation degree of a vertex is defined as the number of different colors to which it is adjacent. The algorithm selects always the vertex with the largest saturation degree. If multiple vertices have the same maximum saturation degree, a vertex of maximum degree in the uncolored subgraph is selected.

Note that the DSatur is not optimal in general, but is optimal for bipartite graphs. Compared to other simpler greedy ordering heuristics, it is usually considered slower but more efficient w.r.t. the number of used colors. See the following papers for details:

• D. Brelaz. New methods to color the vertices of a graph. Communications of ACM, 22(4):251–256, 1979.
• The smallest hard-to-color graph for algorithm DSATUR. Discrete Mathematics, 236:151--165, 2001.

This implementation requires $O(n^2)$ running time and space. The following paper discusses possible improvements in the running time.

• J. S. Turner. Almost all $k$-colorable graphs are easy to color. Journal of Algorithms. 9(1):63--82, 1988.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm

VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>

Constructor Summary

Constructors

Constructor and Description
SaturationDegreeColoring(Graph<V,E> graph) Construct a new coloring algorithm.

Method Summary

Modifier and Type	Method and Description
VertexColoringAlgorithm.Coloring<V>	getColoring() Computes a vertex coloring.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SaturationDegreeColoring

public SaturationDegreeColoring(Graph<V,E> graph)

Construct a new coloring algorithm.

Parameters:

graph - the input graph

Method Detail

getColoring

public VertexColoringAlgorithm.Coloring<V> getColoring()

Computes a vertex coloring.

Specified by:

getColoring in interface VertexColoringAlgorithm<V>

Returns:

a vertex coloring