Efficient Distributed-memory Parallel Algorithms
for Distance-2 Coloring and Their Application to Derivative Computation
Abstract.
The distance-2 graph coloring problem aims at partitioning the vertex
set of a graph into the fewest sets consisting of vertices pairwise at
distance greater than two from each other. Its applications include
derivative computation in numerical optimization and channel
assignment in radio networks. We present efficient,
distributed-memory, parallel heuristic algorithms for this NP-hard
problem as well as for two related problems used in the computation of
Jacobians and Hessians. Parallel speedup is achieved through graph
partitioning, speculative (iterative) coloring, and a BSP-like
organization of parallel computation. Results from experiments
conducted on a PC cluster employing up to 96 processors and using
large-size real-world as well as synthetically generated test graphs
show that the algorithms are scalable. In terms of quality of
solution, the algorithms perform remarkably well---the number of
colors used by the parallel algorithms was observed to be within
$12\%$ of the number used by the sequential counterparts, which in
turn are quite often near optimal. Moreover, the experimental results
show that the parallel distance-2 coloring algorithm compares
favorably with the alternative approach of solving the distance-2
coloring problem on a graph $\G$ by first constructing the square
graph $\G^2$ and then applying a parallel distance-1 coloring
algorithm on $\G^2$. Implementations of the algorithms are made
available via the Zoltan load-balancing library.
|
|