Efficient Parallel Graph Coloring with Prioritization

Lecture Notes in Computer Science (LNCS) 1995

Publication Type: Paper

Repository URL:

Abstract

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.

TextRef

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.

People

- Laxmikant Kale
- B. Richards
- Terry Allen

Research Areas