Seth Pettie
Abstract
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning tree of a graph with n vertices and m edges that runs in time O(T*(m,n)) where T* is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine.Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T* are T*(m,n) = Ω(m) and T*(m,n) = O(m ∙ α(m,n)), where α is a certain natural inverse of Ackermann's function.Even under the assumption that T* is superlinear, we show that if the input graph is selected from Gn,m, our algorithm runs in linear time with high probability, regardless of n, m, or the permutation of edge weights. The analysis uses a new martingale for Gn,m similar to the edge-exposure martingale for Gn,p.
- AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- ALON, N., AND SPENCER, J. 1992. The Probabilistic Method. Wiley, New York.Google Scholar
- BORUVKA, O. 1926. O jistem problemu minimaalnim. Moravske Prirodovedecke Spolecnosti 3, 37-58. (In Czech.)Google Scholar
- BUCHSBAUM, A. L., KAPLAN, H., ROGERS, A., AND WESTBROOK, J. R. 1998. Linear-time pointermachine algorithms for least common ancestors, MST verification, and dominators. In Proceedings of the ACM Symposium on the Theory of Computing. ACM, New York, 279-288. Google Scholar
- CHAZELLE, B. 1997. A faster deterministic algorithm for minimum spanning trees. In Proceedings of the IEEE Symposium on Foundations of Computing Science. IEEE Computer Society Press, Los Alamitos, Calif., 22-31. Google Scholar
- CHAZELLE, B. 2000a. The soft heap: An approximate priority queue with optimal error rate. J. ACM 47, 6, 1012-1027. Google Scholar
- CHAZELLE, B. 2000b. A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47, 6, 1028-1047. Google Scholar
- CHONG, K. W., HAN, Y., AND LAM, T. W. 2001. Concurrent threads and optimal parallel minimum spanning trees algorithm. J. ACM 48, 2, 297-323. Google Scholar
- DIJKSTRA, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269-271.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
- ERD~S, P., AND RENYI, A. 1961. On the evolution of random graphs. Bull. Inst. Internat. Statist. 38, 343-347.Google Scholar
- FREDMAN, M. L., AND TARJAN, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596-615. Google Scholar
- FREDMAN, M., AND WILLARD, D. E. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 3, 533-551. Google Scholar
- GABOW, H. N., 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
- GODDARD, W., KENYON, C., KING, V., AND SCHULMAN, L. 1993. Optimal randomized algorithms for local sorting and set-maxima. SIAM J. Comput. 22, 2, 272-283. Google Scholar
- JARNIK, V. 1930. O jistem problemu minimaalnim. Moravske Prirodovedecke Spolecnosti 6, 57-63. (In Czech.)Google Scholar
- JONES, N. 1997. Computability and Complexity: From a Programming Perspective. MIT Press, Cambridge, Mass. Google Scholar
- KARGER, D. R., KLEIN, P. N., AND TARJAN, R. E. 1995. A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 321-328. Google Scholar
- KARP, R. M., AND TARJAN, R. E. 1980. Linear expected-time algorithms for connectivity problems. J. Algorithms 1, 4, 374-393.Google Scholar
- KING, V. 1997. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 2, 263-270.Google Scholar
- LARMORE, L. L. 1990. An optimal algorithm with unknown time complexity for convex matrix searching. Infor. Process. Lett. 36, 147-151. Google Scholar
- PETTIE, S. 1999. Finding minimum spanning trees in O(m(m; n)) time. Tech. Rep. TR99-23. Univ. of Texas at Austin, Austin, Tex. Google Scholar
- PETTIE, S., AND RAMACHANDRAN, V. 1999. A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. In Proceedings of RANDOM'99. Lecture Notes in Computer Science, vol. 1671. Springer-Verlag, New York, 233-244. Google Scholar
- PETTIE, S., AND RAMACHANDRAN, V. 2002a. Computing shortest paths with comparisons and additions. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 267-276. Google Scholar
- PETTIE, S., AND RAMACHANDRAN, V. 2002b. Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 713-722. Google Scholar
- PRIM, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389- 1401.Google Scholar
- TARJAN, R. E. 1979a. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 2, 110-127.Google Scholar
- TARJAN, R. E. 1979b. Applications of path compression on balanced trees. J. ACM 26, 4, 690-715. Google Scholar
Index Terms
- An optimal minimum spanning tree algorithm
Recommendations
A Divide-and-Conquer Approach for Minimum Spanning Tree-Based Clustering
Due to their ability to detect clusters with irregular boundaries, minimum spanning tree-based clustering algorithms have been widely used in practice. However, in such clustering algorithms, the search for nearest neighbor in the construction of ...
A new algorithm for the minimum spanning tree verification problem
This paper proposes a new algorithm for the minimum spanning tree verification (MSTV) problem in undirected graphs. The MSTV problem is distinct from the minimum spanning tree construction problem. The above problems have been studied extensively, and ...
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'...
Comments