A randomized linear-time algorithm to find minimum spanning trees

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.

REFERENCES

• 1: ~ALON, N., AND SPENCER, J. H. 1992. The Probabilistic Method. Wiley, New York, p. 223.
• 2: ~BOR0VKA, O. 1926. O jistdm probl~mu minimfdnfm. Pr~ca Moravskd P~irodoL,~deckd Spole6nosti ~3, 37 58. (In Czech.)
• 3: Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
• 4: ~HERNOFF, H. 1952. A measure of the asymptotic efficiency for tests of a hypothesis based on ~the sum of observations. Anm Math. Stat. 23, 493-509.
• 5: ~COLE, R., KLEIN, P. N., AND TARJAN, R. E. 1994. A linear-work parallel algorithm for finding ~minimum spanning trees. In Proceedings of the 6th Symposium on Parallel Algorithms and ~Architectures. (Cape May, N.J., June 27-29). ACM, New York, pp. 11-15.
• 6: ~COLE, R., AND VISHKIN, U. 1986. Approximate and exact parallel scheduling with applications to ~list, tree, and graph problems. In Proceedings of the 27th Annual IEEE Symposium on Founda- ~ttons of Computer Science. IEEE, Computer Society Press, Los Alamitos, Calif., pp. 478-491.
• 7: Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
• 8: ~FELLER, W. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley, New ~York.
• 9: ~FREDMAN, M, AND WILLARD, D. E. 1990. Trans-dichotomous algonthms for minimum spanning ~trees and shortest paths. In Proceedings of the 31st Annual IEEE Symposium on Foundations of ~Computer Sctence. IEEE Computer Society Press, Los Alamitos, Calif., pp. 719 725.
• 10: ~GABOW, H. N.~ GALIL, Z., AND SPENCER, T. H. 1984. Efficient implementation of graph ~algorithms using contraction. In Proceedings of the 25th Annual IEEE Symposium on Founda- ~tions of Computer Science. 1EEE Computer Society Press, Los Alamltos, Calif., pp. 347-357.
• 11: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 12: ~GRAHAM, R. L., AND HELL, P. 1985. On the history of the minimum spanning tree problem. ~Ann. Hist. Comput. 7, 43-57.
• 13: ~KARGER, D. R. 1992. Approximating, verifying, and constructing minimum spanning forests. ~Manuscript.
• 14: David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
• 15: ~KARGER, D. R. 1993b. Random sampling in matroids, with applications to graph connectivity ~and minimum spanning trees. In Proceedings of the 34th Annual IEEE Symposium on Founda- ~tions of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 84-93.
• 16: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 17: Valerie King, A Simpler Minimum Spanning Tree Verification Algorithm, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.440-448, August 16-18, 1995
• 18: Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.9-15, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195084]
• 19: KOML0S, J. 1985. Linear verification for spanning trees. Combinatorica 5 57-65.
• 20: ~KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman ~problem. Proc. Amer. Math. Soc. 7, 48-50.
• 21: ~RAGHAVAN, P. 1990. Lecture notes on randomized algorithms. Res. Rep. RC 15340 (#68237). ~Computer Science/Mathematics. IBM Research Division, T. J. Watson Research Center, ~Yorktown Heights, N.Y., p. 54.
• 22: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 23: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms

Keywords:
matroid, minimum spanning tree, randomized algorithm