A randomized linear-time algorithm to find minimum spanning trees
David R. Karger, Philip N. Klein, Robert Endre Tarjan · Journal of the ACM · 1995
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm 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.
Cited by 406 works. doi:10.1145/201019.201022 Open-access PDF
Authors
References
- An introduction to probability theory and its applications
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- The Probabilistic Method
- Data Structures and Network Algorithms
- Applications of Path Compression on Balanced Trees
- On the History of the Minimum Spanning Tree Problem
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- A Survey of Parallel Algorithms for Shared-Memory Machines
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths