A Randomized Linear-Time Algorithm for Finding Minimum Spanning
Trees
Authors: Philip N. Klein and Robert E. Tarjan
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.
DIMACS Home Page