Efficient Parallel Graph Coloring with Prioritization

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.

@incollection{GraphColorLNCS95,
  author = "L. V. Kale and B. H. Richards and T. D. Allen",
  title = "Efficient Parallel Graph Coloring with Prioritization",
  booktitle = "Lecture Notes in Computer Science",
  publisher = "Springer-Verlag",
  year = "1995",
  volume = "1068",
  pages = "190-208",
  month = "August",
}