A randomized linear-time algorithm for finding minimum spanning trees.

Philip N. Klein, Robert Endre Tarjan

Browse the full STOC paper archive.