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

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 and Description
SmallestDegreeLastColoring(Graph<V,E> graph) Construct a new coloring algorithm.

Method Summary

Modifier and Type	Method and Description
protected Iterable<V>	getVertexOrdering() Get the ordering of the vertices used by the algorithm.

Methods inherited from class org.jgrapht.alg.color.GreedyColoring

getColoring

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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