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


 
 

 

A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs)

Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but often have no known efficient parallel implementations. Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but often have no known efficient parallel implementations. The main results of this paper are

  1. A new and practical spanning tree algorithm for symmetric multiprocessors that exhibits parallel speedups on graphs with regular and irregular topologies; and
  2. An experimental study of parallel spanning tree algorithms that reveals the superior performance of our new approach compared with the previous algorithms.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader and G. Cong, ``A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs),'' 18th IEEE Int'l Parallel and Distributed Processing Symp. (IPDPS), Santa Fe, NM, April 26-30, 2004.
  2. D.A. Bader and G. Cong, ``A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs),'' Journal of Parallel and Distributed Computing, 65(9):994-1006, 2005.

Download this report in Adobe PDF

 

 
 

Last updated: August 10, 2005

 




Computational Biology



Parallel Computing



Combinatorics