Paper Info
Title
Distributed-Memory Parallel Algorithms for Distance-2 Coloring and Related Problems in 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 2 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 bulk synchronous parallel-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 numbers of colors used by the parallel algorithms are observed to be very close to the numbers used by their 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 $\mathcal{G}$ by first constructing the square graph $\mathcal{G}^2$ and then applying a parallel distance-1 coloring algorithm on $\mathcal{G}^2$. Implementations of the algorithms are made available via the Zoltan toolkit.
Year
DOI
Venue
2010
10.1137/080732158
SIAM Journal on Scientific Computing
Keywords
DocType
Volume
parallel algorithm,distributed-memory parallel algorithms,distance-2 coloring algorithm,distance-2 coloring,parallel computation,derivative computation,parallel heuristic algorithm,distance-1 coloring algorithm,related problems,distance-2 graph,graph partitioning,parallel speedup,square graph,distance-2 coloring problem,automatic differentiation
Journal
32
Issue
ISSN
Citations 
4
1064-8275
6
PageRank 
References 
Authors
0.62
19
6
Name
Order
Citations
PageRank
Doruk Bozdağ144624.15
Ümit Çatalyürek2624.05
Assefaw H. Gebremedhin319512.54
Fredrik Manne454949.60
Erik G. Boman558738.27
Füsun Özgüner61443107.84