Live Webcast 15th Annual Charm++ Workshop

Efficient Parallel Graph Coloring with Prioritization
| Laxmikant Kale | B. Richards | Terry Allen
Lecture Notes in Computer Science (LNCS) 1995
Publication Type: Paper
Repository URL:
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.
L. V. Kale and B. H. Richards and T. D. Allen, "Efficient Parallel Graph Coloring with Prioritization", Lecture Notes in Computer Science, Publ: Springer-Verlag, vol. 1068, August 1995, pp. 190-208.
Research Areas