Package com.jgalgo.alg.color

Class 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:
    Wikipedia

    • Constructor Detail

      • ColoringRecursiveLargestFirst

        public ColoringRecursiveLargestFirst()
        Create a new coloring algorithm object.

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