A randomized linear-time algorithm for finding minimum spanning trees
Philip N. Klein, Robert Endre Tarjan · ACM Symposium on Theory of Computing (STOC) · 1994
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. 1 Introduction We consider the problem of finding a minimum spanning tree in a connected graph with real-valued edge weights. This problem has a long and rich history; the first fully realized algorithm was devised by Boruvka in the 1920's [3]. An informative survey paper by Graham and Hell [9] describes the history of the problem up to 1985. In the last two decades faster and faster algorithms were found, the fastest being an algorithm of Gabow, Galil, and Spencer [7] (see also [8]), with a running time of O(m log fi(m; n)) on a ...
Cited by 51 works. doi:10.1145/195058.195084
Authors
References
- 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
- Time bounds for selection
- 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