David R. Karger
Philip N. Klein
Robert E. Tarjan
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.
- ~ALON, N., AND SPENCER, J. H. 1992. The Probabilistic Method. Wiley, New York, p. 223.Google Scholar
- ~BOR0VKA, O. 1926. O jistdm probl~mu minimfdnfm. Pr~ca Moravskd P~irodoL,~deckd Spole6nosti ~3, 37 58. (In Czech.)Google Scholar
- ~CHERIYAN, J., HAGERUP, T., AND MEHLHORN, K. 1990. Can a maximum flow be computed in ~O(nm) time? In Proceedings of the 17th hzternational Colloquium on Automata, Languages, and ~Programming. Lecture Notes in Computer Science, vol. 443. Springer-Verlag, New York, pp. ~235-248. Google Scholar
- ~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.Google Scholar
- ~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.Google Scholar
- ~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.Google Scholar
- ~DIXON, B., RAUCH, M., AND TARJAN, R. E. 1992. Verification and sensitivity analysis of ~minimum spanning trees in linear time. SIAM J. Comput. 21, 1184-1192. Google Scholar
- ~FELLER, W. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley, New ~York.Google Scholar
- ~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.Google Scholar
- ~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.Google Scholar
- ~GABOW, H. $., GALIL, Z., SPENCER, T., AND TARJAN, R. E. 1986. Efficient algorithms for finding ~minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109-122. Google Scholar
- ~GRAHAM, R. L., AND HELL, P. 1985. On the history of the minimum spanning tree problem. ~Ann. Hist. Comput. 7, 43-57.Google Scholar
- ~KARGER, D. R. 1992. Approximating, verifying, and constructing minimum spanning forests. ~Manuscript.Google Scholar
- ~KARGER, D. R. 1993a. Global rain-cuts in RNC and other ramifications of a simple mincut ~algorithm. In Proceedings of the 4th Annual ACM-SIAM Sympostum on Discrete Algortthms. ~ACM, New York, pp. 21-30. Google Scholar
- ~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.Google Scholar
- ~KARP, R. M., AND RAMACHANDRAN, V. 1990. A survey of parallel algorithms for shared-memory ~machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, ~J. van Leeuwen, ed. MIT Press, Cambridge, Mass., pp. 869 941. Google Scholar
- ~KING, V. 1995. A simpler minimum spanning tree verification algorithm. In Proceedings of the ~Workshop on Algorithms and Data Structures, to appear. Google Scholar
- ~KLEIN, P. N., AND TARJAN, R. E. 1994. A randomized linear-time algorithm for finding minimum ~spanning trees. In Proceedings' of the 26th Annual ACM Symposium on Theory of Computing. ~(Montreal, Que., Canada, May 23-25). ACM, New York, pp. 9-15. Google Scholar
- KOML0S, J. 1985. Linear verification for spanning trees. Combinatorica 5 57-65.Google Scholar
- ~KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman ~problem. Proc. Amer. Math. Soc. 7, 48-50.Google Scholar
- ~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.Google Scholar
- ~TARJAN, R. m. 1979. Applications of path compression on balanced trees. J. ACM 26, 4 (Oct.), ~690-715. Google Scholar
- ~TARJAN, R. E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied ~Mathematics, Philadelphia, Pa., Chap. 6. Google Scholar
Index Terms
- A randomized linear-time algorithm to find minimum spanning trees
Recommendations
The expected complexity of Prim's minimum spanning tree algorithm
We study the expected performance of Prim's minimum spanning tree (MST) algorithm implemented using ordinary heaps. We show that this implementation runs in linear or almost linear expected time on a wide range of graphs. This helps to explain why Prim'...
Time-communication trade-offs for minimum spanning tree construction
ICDCN '17: Proceedings of the 18th International Conference on Distributed Computing and NetworkingThis paper concerns the problem of constructing a minimum spanning tree (MST) in a synchronous distributed network with n nodes, where each node knows only the identities of itself and its neighbors. We assume the CONGEST model where messages are of ...
Distributed verification of minimum spanning trees
The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the ...
Reviews
Ruay-Shiung Chang
A randomized algorithm for finding a minimum spanning tree is described. The algorithm runs in O E time with high probability in the restricted random-access model. Whether an O E deterministic algorithm exists is still open. Interestingly, this randomized algorithm incorporates steps of the oldest (and simplest) minimum spanning tree algorithm. It again demonstrates the idea that a simpler algorithm is easier to analyze probabilistically. Given the fast processors that are currently available, however, all low-order polynomial algorithms are efficient enough. What we hope for is efficient randomized algorithms for solving hard problems, such as NP-complete problems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments