Parallel and On-line Graph Coloring
Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.
We discover a surprising connection between graph coloring in two
orthogonal paradigms: parallel and on-line computing. We present a
randomized on-line coloring algorithm with a performance ratio of
O(n/log n), an improvement of sqrt(log n) factor over the previous
best known algorithm of Vishwanathan. Also, from the same principles,
we construct a parallel coloring algorithm with the same performance
ratio, for the first such result. As a byproduct, we obtain a
parallel approximation for the independent set problem.