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 typeE
- 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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm
VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
-
-
Field Summary
-
Fields inherited from class org.jgrapht.alg.color.GreedyColoring
graph, SELF_LOOPS_NOT_ALLOWED
-
-
Constructor Summary
Constructors Constructor Description SmallestDegreeLastColoring(Graph<V,E> graph)
Construct a new coloring algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected java.lang.Iterable<V>
getVertexOrdering()
Get the ordering of the vertices used by the algorithm.-
Methods inherited from class org.jgrapht.alg.color.GreedyColoring
getColoring
-
-
-
-
Method Detail
-
getVertexOrdering
protected java.lang.Iterable<V> getVertexOrdering()
Get the ordering of the vertices used by the algorithm.- Overrides:
getVertexOrdering
in classGreedyColoring<V,E>
- Returns:
- the ordering of the vertices used by the algorithm
-
-