93-71 A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees

DIMACS TR: 93-71

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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-71.ps

DIMACS Home Page