Graph coloring in a class of parallel local algorithms
Vladimir A. Evstigneev, Y. Tursunbay kyzy · Numerical Analysis and Applications · 2011
A way of improving the performance of a distributed algorithm is rendering a coloring strategy into an algorithm known as efficient in the nondistributed case. In this paper it is shown that certain sequential coloring algorithm heuristics like largest-first (LF), smallest-last (SL), and saturation largest-first (SLF), as applied to some classes of graphs and to special cases of vertex coloring in distributed algorithms, produce an optimal or near-optimal coloring.