A randomized linear-time algorithm to find minimum spanning trees
David R. Karger, Philip N. Klein, Robert Endre Tarjan · Journal of the ACM · 1995
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.