A Parallel Distance-2 Graph Coloring Algorithm
for Distributed Memory Computers
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. Application example include numerical optimization and channel
assignment. We present the first distributed-memory heuristic algorithm
for this NP-hard problem. Parallel speedup is achieved through graph
partitioning, speculative (iterative) coloring, and a BSP-like
organization of computation. Experimental results show that the
algorithm is scalable, and compares favorably with an alternative
approach---solving the 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$.
Full paper in PDF
|