An optimal minimum spanning tree algorithm

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 G_n,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 G_n,m similar to the edge-exposure martingale for G_n,p.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ALON, N., AND SPENCER, J. 1992. The Probabilistic Method. Wiley, New York.
• 3: BORUVKA, O. 1926. O jistem problemu minimaalnim. Moravske Prirodovedecke Spolecnosti 3, 37-58. (In Czech.)
• 4: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.279-288, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276764]
• 5: Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
• 6: Bernard Chazelle, The soft heap: an approximate priority queue with optimal error rate, Journal of the ACM (JACM), v.47 n.6, p.1012-1027, Nov. 2000 [doi>10.1145/355541.355554]
• 7: Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
• 8: Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001 [doi>10.1145/375827.375847]
• 9: DIJKSTRA, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269-271.
• 10: 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]
• 11: ERD~S, P., AND RENYI, A. 1961. On the evolution of random graphs. Bull. Inst. Internat. Statist. 38, 343-347.
• 12: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 13: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 14: 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]
• 15: GRAHAM, R. L., AND HELL, P. 1985. On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7, 43-57.
• 16: Wayne Goddard , Claire Kenyon , Valerie King , Leonard J. Schulman, Optimal randomized algorithms for local sorting and set-maxima, SIAM Journal on Computing, v.22 n.2, p.272-283, April 1993 [doi>10.1137/0222020]
• 17: JARNIK, V. 1930. O jistem problemu minimaalnim. Moravske Prirodovedecke Spolecnosti 6, 57-63. (In Czech.)
• 18: Neil D. Jones, Computability and complexity: from a programming perspective, MIT Press, Cambridge, MA, 1997
• 19: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 20: KARP, R. M., AND TARJAN, R. E. 1980. Linear expected-time algorithms for connectivity problems. J. Algorithms 1, 4, 374-393.
• 21: KING, V. 1997. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 2, 263-270.
• 22: L. L. Larmore, An optimal algorithm with unknown time complexity for convex matrix searching, Information Processing Letters, v.36 n.3, p.147-151, Nov. 1990 [doi>10.1016/0020-0190(90)90084-B]
• 23: Seth Pettie, Finding Minimum Spanning Trees in O(m alpha(m,n)) Time, University of Texas at Austin, Austin, TX, 1999
• 24: Seth Pettie , Vijaya Ramachandran, A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.233-244, August 08-11, 1999
• 25: Seth Pettie , Vijaya Ramachandran, Computing shortest paths with comparisons and additions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.267-276, January 06-08, 2002, San Francisco, California
• 26: Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
• 27: PRIM, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389- 1401.
• 28: TARJAN, R. E. 1979a. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 2, 110-127.
• 29: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
Graph algorithms, minimum spanning tree, optimal complexity