Barr, R. S.; Helgaon, R. V.; Kennington, J. L. Minimal spanning trees: An empirical investigation of parallel algorithms. (English) Zbl 0681.68086 Parallel Comput. 12, No. 1, 45-52 (1989). 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. Cited in 2 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees 68N25 Theory of operating systems 68N99 Theory of software Keywords:minimum spanning tree problem; graph theory; performance; measurements; Prim’s algorithm; Sollin’s algorithm; Kruskal’s algorithm; Sequent Symmetry S81 multicomputer PDFBibTeX XMLCite \textit{R. S. Barr} et al., Parallel Comput. 12, No. 1, 45--52 (1989; Zbl 0681.68086) Full Text: DOI