Scalable, Shared Memory Parallel Graph Coloring Heuristics
Reports in Informatics No. 181, December 1999, Department of
Informatics, University of Bergen, Norway.
Abstract
Finding a good graph coloring quickly is often a crucial phase in the
development of efficient, parallel algorithms for many scientific and
engineering applications. In this paper we consider the problem of
solving the graph coloring problem itself in parallel. We present a
simple and fast parallel graph coloring heuristic that is well suited
for shared memory programming and yields an almost linear speedup on
the PRAM model. We also present a second heuristic that improves on
the number of colors used. The heuristics have been implemented using
OpenMP. Experiments conducted on an SGI Cray Origin 2000 using very
large graphs from finite element methods and eigen value computations
validate the theoretical run-time analysis.
Download
Back