Package com.jgalgo.alg.color

Class ColoringDSatur

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:

  • Constructor Details

    • ColoringDSatur

      public ColoringDSatur()
      Create a new coloring algorithm object.

      Please prefer using ColoringAlgo.newInstance() to get a default implementation for the ColoringAlgo interface.