A linear-work parallel algorithm for finding minimum spanning trees.

R.J. Cole, P.N. Klein, R.E. Tarjan.

Proceedings of the Sixth Annual Symposium on Parallel Algorithms and Architectures, 1994, 11-15.

We give the first linear-work parallel algorithm for finding a minimum spanning tree. It is a randomized algorithm, and requires expected O(2^{log^* n} log n) time. It is a modification of the sequential linear-time algorithm of Klein and Tarjan.