ColoringDSatur (JGAlgo - Parent 0.5.1-SNAPSHOT API)

java.lang.Object
- com.jgalgo.alg.color.ColoringAlgoAbstract
- - com.jgalgo.alg.color.ColoringDSatur

All Implemented Interfaces:

ColoringAlgo
```
public class ColoringDSatur
extends ColoringAlgoAbstract
```
The D-Satur coloring algorithm.
The Saturation Degree (D-Satur) coloring algorithm is a greedy algorithm, namely it examine the vertices in some order and assign for each vertex the minimum (integer) color which is not used by its neighbors. It differ from other greedy coloring algorithms by the order it examine the vertices: the next vertex to be colored is the vertex with the highest number of colors in its neighborhood (adjacent vertices), also called saturation degree.
The algorithm runs in \(O(m \log n)\) time assuming the number of colors is constant.
Note that the result is an approximation for the minimum number of colors, as finding an optimal coloring is an NP-hard problem.

Author:

Barak Ugav

See Also:

Wikipedia

- Constructor Summary
  
  Constructors
  Constructor Description
  
  ColoringDSatur()
  Create a new coloring algorithm object.
- Method Summary
  - Methods inherited from class com.jgalgo.alg.color.ColoringAlgoAbstract
    computeColoring
  - Methods inherited from class java.lang.Object
    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - ColoringDSatur
```
public ColoringDSatur()
```
    Create a new coloring algorithm object.
    Please prefer using ColoringAlgo.newInstance() to get a default implementation for the ColoringAlgo interface.