Efficient Parallel Graph Coloring with Prioritization
| Laxmikant Kale | Ben H.Richards | Terry Allen
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.
TextRef
People
Research Areas