David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs

Minimum Spanning Tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to implement or perform well only on special graphs with regular structure. In this paper we design and implement four parallel MST algorithms (three variations of Borůvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the best sequential algorithm. In fact, our algorithms also solve the minimum spanning forest problem. We provide an experimental study of our algorithms on symmetric multiprocessors such as IBM's p690/Regatta and Sun's Enterprise servers. Our new implementation achieves good speedups over a wide range of input graphs with regular and irregular structures, including the graphs used by previous parallel MST studies. For example, on an arbitrary random graph with 1M vertices and 20M edges, our new approach achieves a speedup of 5 using 8 processors. The source code for these algorithms is freely available from our web site.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader and G. Cong, ``Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs,'' 18th IEEE Int'l Parallel and Distributed Processing Symp. (IPDPS), Santa Fe, NM, April 26-30, 2004.
  2. D.A. Bader and G. Cong, ``Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs,'' Journal of Parallel and Distributed Computing, 66(11):1366-1378, 2006.

Download this report in Adobe PDF

 

 
 

Last updated: October 27, 2007

 




Computational Biology



Parallel Computing



Combinatorics