NPAC Technical Report SCCS-666
A Comparison of Parallel Graph Coloring Algorithms
James Allwright, Rajesh Bordawekar, Paul Coddington, Kivanc Dincer, Chris Martin
Submitted May 1 1994
Abstract
Dynamic irregular triangulated meshes are used in adaptive grid
partial differential equation (PDE) solvers, and in simulations of
random surface models of quantum gravity in physics and
cell membranes in biology.
Parallel algorithms for random surface simulations and adaptive grid PDE
solvers require coloring of the triangulated mesh, so that neighboring
vertices are not updated simultaneously.
Graph coloring is also used in iterative parallel algorithms
for solving large irregular sparse matrix equations.
Here we introduce some parallel graph coloring algorithms based on
well-known sequential heuristic algorithms, and compare them with some
existing parallel algorithms.
These algorithms are implemented on both SIMD and MIMD parallel architectures
and tested for speed, efficiency, and quality (the average number of
colors required) for coloring random triangulated meshes
and graphs from sparse matrix problems.