A randomized linear-time algorithm to find minimum spanning trees
- 1 March 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (2) , 321-328
- https://doi.org/10.1145/201019.201022
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- A simpler minimum spanning tree verification algorithmPublished by Springer Nature ,1995
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear TimeSIAM Journal on Computing, 1992
- Parallel Algorithms for Shared-Memory MachinesPublished by Elsevier ,1990
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- Linear verification for spanning treesCombinatorica, 1985
- On the History of the Minimum Spanning Tree ProblemIEEE Annals of the History of Computing, 1985
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983
- Applications of Path Compression on Balanced TreesJournal of the ACM, 1979
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952