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.