A Scalable
Parallel Graph Coloring Algorithm
for Distributed Memory Computers
Abstract.
In large-scale parallel
applications a graph coloring is often carried out to schedule
computational tasks. In this paper, we describe a new
distributed-memory algorithm for doing the coloring itself in parallel.
The algorithm operates in an iterative fashion; in each round vertices
are speculatively colored based on limited information, and then a set
of incorrectly colored vertices, to be recolored in the next round, is
identified. Parallel speedup is achieved in part by reducing the
frequency of communication among processors. Experimental results on a
PC cluster using up to 16 processors show that the algorithm is
scalable.
Full paper in PDF
|
|