Package org.graph4j.coloring

Class SmallestDegreeLastColoring

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.GreedyColoringBase

org.graph4j.coloring.GreedyColoring

org.graph4j.coloring.SmallestDegreeLastColoring

All Implemented Interfaces:

ColoringAlgorithm

public class SmallestDegreeLastColoring
extends GreedyColoring

The smallest-last greedy algorithm computes the vertex ordering from the end to the beginning. At each step, the node of minimum degree in the current graph is selected and then it is removed from the graph. So, the first vertex to be selected is the one with the smallest degree in the graph, and it is stored at the end of the ordering. Suppose that the vertices V'={vi+1,..., vn} have been already selected, the next vertex to be chosen is v_i in V-V' such that the degree of v_i in the subgraph induced by the remaining vertices V-V' is minimal.

Author:

Cristian Frăsinaru

See Also:

• SmallestDegreeLastOrdering

Field Summary

Fields inherited from class org.graph4j.coloring.GreedyColoring

pos, vertexOrdering

Fields inherited from class org.graph4j.coloring.GreedyColoringBase

colors, numColors, used

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
SmallestDegreeLastColoring(Graph graph)

Method Summary

Methods inherited from class org.graph4j.coloring.GreedyColoring

hasUncoloredVertices, init, nextUncoloredVertex

Methods inherited from class org.graph4j.coloring.GreedyColoringBase

findColoring, findColoring, markUsedColor, update

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graph4j.coloring.ColoringAlgorithm

getGraph, getHeuristicColoring, getLowerBound, getMaximalClique, isOptimalityEnsured, isSolvingComponents, isStoppingOnFailure, isValid

Constructor Details

SmallestDegreeLastColoring

public SmallestDegreeLastColoring(Graph graph)