A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees

Abstract:

We present a randomized linear-time algorithm for finding a minimum
spanning tree in a connected graph with edge weights. The algorithm
is a modification of one proposed by Karger and 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.