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
A new and practical spanning tree algorithm for symmetric
multiprocessors that exhibits parallel speedups on graphs with
regular and irregular topologies; and
An experimental study of parallel spanning tree algorithms that
reveals the superior performance of our new approach compared with
the previous algorithms.
