Graph Coloring Algorithms
For any planar graph, 4 colors. But for non-planar, more colors are needed….known as an NP-Hard problem.
Sequential algorithms: Largest-Degree-First, Smallest-Degree-Last can be readily parallelized.
Based on the simple observation that any independent set of vertices can be colored in parallel, independent set is a set of vertices that no two of them are neighbors. Shown in the graph below:
Graph partitioning problem…
An example is here:
The lowest available colour: the smallest color that has not already been assigned to a neighboring vertex.
Very similar to Jones-Plassmann, the only difference is, initially not random choosing.
First find out the degrees.Random numbers are only used to resolve conicts between neighboring vertices having the same degree.
Coloring happened in an order of decreasing degree.
It is aimed to use fewer colours than the J-P one.
” A vertex with i colored neighbors will require at most color i+ 1. The Largest-Degree-First algorithm aims to keep the maximum value of i as small as possible throughout the computation, so that there is a better chance of using only a small number of colors.”
TinkerPop 3 with Java: Jones-Plassmann graph coloring:
Please Find Jones-Plassmann in my Github
So basically, the Gibbs Sampling is transferred to a Graph Coloring problem, which is, how to separate a graph into groups, with the neighors are exclusive.
After I finished evaluation, I will update this post 🙂
This is the learning notes of A Comparison of Parallel Graph Coloring Algorithms (Reference).