V
- the graph vertex typeE
- the graph edge typepublic class RLFColoring<V,E> extends Object implements org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>
The RLF algorithm was originally designed by F. Leighton (1979) in A Graph Coloring Algorithm for Large Scheduling Problems, in part for use in constructing solutions to large timetabling problems. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color class C is one with a maximum number of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C.
This implementation is based on the original algorithm pseudocode provided in 'A new efficient RLF-like Algorithm for the Vertex Coloring Problem' : "for practical purposes, the RLF algorithm, if programmed properly, exhibits an O(n2) time dependence for many applications".
RLF exhibits similar chromatic performance compared to DSATUR. In 'A Performance Comparison of Graph Coloring Algorithms' RLF tended to produce the best colorings (as measured by color number), marginally ahead of DSATUR.
Improved drop-in replacement heuristics for RLF are explored in 'A new efficient RLF-like Algorithm for the Vertex Coloring Problem' (though most increase runtime complexity).
Constructor and Description |
---|
RLFColoring(org.jgrapht.Graph<V,E> graph) |
RLFColoring(org.jgrapht.Graph<V,E> graph,
long seed) |
Modifier and Type | Method and Description |
---|---|
org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V> |
getColoring() |
Copyright © 2023. All rights reserved.