Package com.jgalgo.alg.color

Class ColoringRecursiveLargestFirst

java.lang.Object
com.jgalgo.alg.color.ColoringAlgoAbstract
com.jgalgo.alg.color.ColoringRecursiveLargestFirst
All Implemented Interfaces:
ColoringAlgo
public class ColoringRecursiveLargestFirst extends ColoringAlgoAbstract
The Recursive Largest First coloring algorithm.

The Recursive Largest First (RLF) coloring algorithm assign colors to vertices in the following way: identify a maximal independent set \(S\), assign to \(S\) a new color, repeat as long as there are uncolored vertices. The maximal independent set is chosen in a greedy fashion; the vertex with the maximum number of uncolored vertices is first added to \(S\), than vertices are added one after another by choosing the vertex with maximum number of neighbors adjacent to vertices in \(S\), until no more vertices can be added to \(S\) (all uncolored vertices are adjacent to vertices in \(S\)).

The algorithm runs in time \(O(n m)\).

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

    • ColoringRecursiveLargestFirst

      public ColoringRecursiveLargestFirst()
      Create a new coloring algorithm object.

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