Efficient Parallel Graph Coloring with Prioritization

International Workshop on Parallel Symbolic Languages and Systems (PSLS) 1996

Publication Type: Talk

Repository URL:

Summary

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 talk, 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.

People

- Laxmikant Kale
- Ben H.Richards
- Terry Allen

Research Areas