|
TR-436-93
A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees |
|
| Authors: | Klein, Philip N., Tarjan, Robert E. |
| Date: | October 1993 |
| Pages: | 9 |
| Download Formats: | [Postscript] |
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. |
|