A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees
Report ID:
TR-436-93
Authors:
Date:
September 1993
Pages:
9
Download Formats:
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.