Efficient Parallel Graph Coloring with Prioritization
Authors:
L. V. Kale and B. H. Richards and T. D. Allen
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
Lecture Notes in Computer Science, vol 1068, August 1995, pp 190-208. Springer-Verlag.
Graph coloring is an interesting problem that is intuitive and simple to formulate, yet difficult to solve efficiently. The applications of graph coloring are numerous, ranging from scheduling to solving linear systems. Because graph coloring is computationally intensive, a parallel algorithm is desirable. In this paper, we present a set of parallel graph coloring heuristics and describe their implementation in an environment supporting machine-independent parallel programming. The heuristics are intended to provide consistent, monotonically increasing speedups as the number of processors is increased. We present some performance results that demonstrate the effectiveness of our heuristics and the utility of our approach.