AbstractWe 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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory; G.3 [Probability and Statistics] -- probabilistic algorithms (including Monte Carlo); I.5.3 [Pattern Recognition]: Clustering
General Terms: Algorithms
Additional Key Words and Phrases: Matroid, minimum spanning tree, network, randomized algorithm
Selected papers that cite this one
- Timothy M. Chan. Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees. Information Processing Letters, 67(6):303-304, 30 September 1998.
- Bernard Chazelle. A faster deterministic algorithm for minimum spanning trees. In 38th Annual Symposium on Foundations of Computer Science, pages 22-31, Miami Beach, Florida, 20-22 October 1997. IEEE.
- David Eppstein, Zvi Galil, and Amnon Nissenzweig. Sparsification -- a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, September 1997.
- David Fernández-Baca and Giora Slutzki. Linear-time algorithms for parametric minimum spanning tree problems on planar graphs. Theoretical Computer Science, 181(1):57-74, 15 July 1997.
- D. Fernàndez-Baca, G. Slutzki and D. Eppstein. Using Sparsification for Parametric Minimum Spanning Tree Problems Nordic Journal of Computing, 3(4):352-366, Winter 1996.
- Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, and Gregory B. Sorkin. Constructing computer virus phylogenies. Journal of Algorithms, 26(1):188-208, January 1998.
- Jens Gustedt. Minimum spanning trees for minor-closed graph classes in parallel. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 421-431, Paris France, 25-27 February 1998. Springer.
- Shay Halperin and Uri Zwick. An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM. Journal of Computer and System Sciences, 53(3):395-416, December 1996.
- David R. Karger. Minimum cuts in near-linear time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 56-63, Philadelphia, Pennsylvania, 22-24 May 1996.
- Stavros G. Kolliopoulos and Clifford Stein. Finding real-valued single-source shortest paths in o(n^3) expected time. Journal of Algorithms, 28(1):125-141, July 1998.
- Vincenzo Liberatore. Matroid decomposition methods for the set maxima problem. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 400-409, San Francisco, California, 25-27 January 1998.
- Mikkel Thorup. Floats, integers, and single source shortest paths. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 14-24, Paris France, 25-27 February 1998. Springer.
Selected references
- Richard Cole and Uzi Vishkin. Approximate and exact parallel scheduling with applications to list, tree and graph problems. In 27th Annual Symposium on Foundations of Computer Science, pages 478-491, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.
- Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 719-725, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Harold N. Gabow, Zvi Galil, and Thomas H. Spencer. Efficient implementation of graph algorithms using contraction. In 25th Annual Symposium on Foundations of Computer Science, pages 347-357, Singer Island, Florida, 24-26 October 1984. IEEE.
- David R. Karger. Random sampling in matroids, with applications to graph connectivity and minimum spanning trees. In 34th Annual Symposium on Foundations of Computer Science, pages 84-93, Palo Alto, California, 3-5 November 1993. IEEE.
- Philip N. Klein and Robert E. Tarjan. A randomized linear-time algorithm for finding minimum spanning trees. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 9-15, Montréal, Québec, Canada, 23-25 May 1994.
- Robert Endre Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26(4):690-715, October 1979.