Module org.jgrapht.core
Package org.jgrapht.alg.color

Class SmallestDegreeLastColoring<V,E>

java.lang.Object
org.jgrapht.alg.color.GreedyColoring<V,E>
org.jgrapht.alg.color.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 Details

    • SmallestDegreeLastColoring

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

  • Method Details

    • 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