Package org.jgrapht.alg.color

Class SmallestDegreeLastColoring<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexColoringAlgorithm<V>
    public class SmallestDegreeLastColoring<V,​E>
extends GreedyColoring<V,​E>
    The smallest degree last greedy coloring algorithm.

    This is the greedy coloring algorithm with the smallest-last ordering of the vertices. The basic idea is as follows: Assuming that vertices $v_{k+1}, \dotso, v_n$ have been already selected, choose $v_k$ so that the degree of $v_k$ in the subgraph induced by $V - $(v_{k+1}, \dotso, v_n)$ is minimal. See the following paper for details.

    • D. Matula, G. Marble, and J. Isaacson. Graph coloring algorithms in Graph Theory and Computing. Academic Press, 104--122, 1972.
    Author:
    Michael Behrisch, Dimitrios Michail

    • Constructor Detail

      • SmallestDegreeLastColoring

        public SmallestDegreeLastColoring​(Graph<V,​E> graph)
        Construct a new coloring algorithm.
        Parameters:
        graph - the input graph

    • Method Detail

      • getVertexOrdering

        protected Iterable<V> getVertexOrdering()
        Get the ordering of the vertices used by the algorithm.
        Overrides:
        getVertexOrdering in class GreedyColoring<V,​E>
        Returns:
        the ordering of the vertices used by the algorithm