Practical parallel algorithms for minimum spanning trees

F. Dehne, Silvia Götz

2002 · 37 citations · 23 references

Concepts

Abstract

We study parallel algorithms for computing the minimum spanning tree of a weighted undirected graph G with n vertices and m edges. We consider an input graph G with m/n/spl ges/p, where p is the number of processors. For this case, we show that simple algorithms with data-independent communication patterns are efficient both in theory and in practice. The algorithms are evaluated theoretically using Valiant's (1990) BSP model of parallel computation and empirically through implementation results.

References

23