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