An Efficient Parallel Minimum Spanning Tree Algorithm on Message Passing Parallel Machine
Guang Wang · 2000
An efficient parallel minimum spanning tree is proposed based on the classical Boruvka's algorithm on message passing parallel machine. Three methods were used to improve its efficiency, including two phase union and packaged contraction for reducing communication costs, and the balanced data distribution for computation balance in each processor. The computation and communication costs of the algorithm are O(n 2/p) and O((t sp+t wn)n/p) . On Dawning 1000 parallel machine, it gets a speedup of 12 on 16 processors with a sparse graph of 10 000 vertices.