×

Minimal spanning trees: An empirical investigation of parallel algorithms. (English) Zbl 0681.68086

Summary: The objective of this investigation is to empirically test parallel algorithms for finding minimal spanning trees. Computational tests were conducted on three serial versions of Prim’s algorithm, a serial version of Prim’s algorithm, and a serial version of Sollin’s algorithm. For complete graphs, our implementation of the Prim algorithm is best. As the graph density is reduced, our implementation of Kruskal’s algorithm is superior, and for very sparse graphs, the Sollin algorithm dominates. Parallel implementations of both the Prim algorithm and the Sollin algorithm were empirically tested on a Sequent Symmetry S81 multicomputer. In tests involving ten processors, the speedups ranged from a low of 2.79 to a high of 6.81.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68N25 Theory of operating systems
68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI