V- the graph vertex type
E- the graph edge type
public class SaturationDegreeColoring<V,E> extends Object implements VertexColoringAlgorithm<V>
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:
This implementation requires $O(n^2)$ running time and space. The following paper discusses possible improvements in the running time.
|Constructor and Description|
Construct a new coloring algorithm.
|Modifier and Type||Method and Description|
Computes a vertex coloring.
Copyright © 2020. All rights reserved.