Finding minimum spanning forests in logarithmic time and linear work using random sampling.

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

Proceedings of the Eighth Annual Symposium on Parallel Algorithms and Architectures, 1996, 243-250.

We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2^{log^* n} off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms.