Computing minimum spanning trees efficiently

ABSTRACT

A ubiquitous problem in mathematical programming is the calculation of minimum spanning trees. Minimum spanning tree algorithms find application in such diverse areas as: least cost electrical wiring, minimum cost connecting communication and transportation networks, network reliability problems, minimum stress networks, clustering and numerical taxonomy, algorithms for solving traveling salesman problems, and multiterminal network flows. It is therefore important to know how to carry out these computations as efficiently as possible.The problem is to find a spanning subtree of a given connected network which has minimum total length. Kruskal in 1956 showed that a "greedy" algorithm could be used; that is, if one looks at arcs in order of increasing length the first tree that can be formed is a minimum spanning tree. Shortly thereafter Prim and Dijkstra suggested another algorithm which appeared to be more efficient. Recent work suggests that a suitable implementation of Kruskal's Algorithm is computationally more efficient in a number of interesting cases, in particular when the network under consideration is sparse.A modification of Kruskal's Algorithm for the solution to the MST problem is presented and is compared with Prim's Algorithm. Prim's Algorithm is shown to have an upper bound on the number of calculations on the order of NN², when applied to a network with NN nodes, regardless of the number of arcs in the network. The modification of Kruskal's Algorithm is shown to have an upper bound on the order of NA log2 NA calculations, where NA is the number of arcs in the network. Thus for sparse networks a dramatic reduction in execution time can be obtained by the use of Kruskal's Algorithm. The effect is enhanced by the fact that Prim's Algorithm achieves its upper bound while the Kruskal modification, in general, does not. Modifications to both Prim's and Kruskal's Algorithms are introduced which give significant improvements for the complete range of sparseness.The relative merit of each algorithm is a function of sparseness of the network, the form in which the problem data is represented, the tradeoff between computation speed and storage requirements, the amount of time one wants to spend in coding, as well as many other factors. The interaction of these factors in choosing the appropriate algorithms for important classes of applications will be discussed in detail.

REFERENCES

• 1: H. Loberman , A. Weinberger, Formal Procedures for Connecting Terminals with a Minimum Total Wire Length, Journal of the ACM (JACM), v.4 n.4, p.428-437, Oct. 1957 [doi>10.1145/320893.320896]
• 2: Kalaba, R., "Graph Theory and Automatic Control", in Applied Combinatorial MatheMatics, E. Beckenbach (ed.) Wiley, 1964
• 3: Gower, J. C. and Ross, G. J. S., "Minimum Spanning Trees and Single Linkage Cluster Analysis", Appl. Statistics, Vol. 18, No.1, 54-64, 1969
• 4: Zahn, C. T., "Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters", IEEE Trans. on Computers, C-20, No.1, January, 1971
• 5: Van Slyke, R. and Frank, H., "Network Reliability Analysis I", Networks, Vol. 1, No. 3, 1972
• 6: Gomory, R. E. and Hu, T. C., "MultiTerminal Network Flows", J.SIAM, 9, No.4, December, 1961
• 7: Held, M. and Karp, R., "The Travelling Salesman Problem and Minimum Spanning Trees", ORSA, 18, No.6, 1138-1162, Nov.-Dec. 1970
• 8: Held, M. and Karp, R.,"The Travelling Salesman Problem and Minimum Spanning Trees: II", Mathematical Proqramminq, 1, No. 1, 1971.
• 9: Kruskal, Joseph B., Jr. "On the Shortest Spanning Subtree of a graph and the Travelling Salesman Problem", Proc. Amer. Math. Soc., 7, 48-50, 1956
• 10: Choquet, G., "Etude de Certains Reseau de Route," C.R.Ac.Sc.,206, 310, 1938
• 11: Borûvka, Otaka, "On a Minimal Problem", Prace Moravské Pridovedecké Spodecnosti, 3, 1926.
• 12: Edmonds, J. "Matroids and the Greedy Algorithm", Mathematical Programming, 1, No. 2, 1971
• 13: Obruca, A., "Algo. 1 Mintree" Computer Bulletin, p. 67, Sept. 1964
• 14: Prim, R. C., "Shortest Connection Networks and Some Generalizations," Bell System Tech. J., 1389-1401, November,1957
• 15: Dijkstra, E. W., "A Note on Two Problems in Connection with Graphs", Numerishe Mathematik, 1, 269-271, 1959
• 16: Rosenstiehl, P., "L'Arbre Minimum d'un Graphe", in Theory of Graphs, P. Rosenstiehl, ed., 1967, Gordon and Breach, N.Y.
• 17: Floyd, Robert W., "Treesort", Algorithm 113, ACM Collected Algorithms, August 1962
• 18: Floyd, Robert W., "Treesort 3", Algorithm 245, ACM Collected Algorithms December, 1964
• 19: Williams, J. W. J., "Heapsort", Algorithm 232, ACM Collected Algorithm, January, 1964
• 20: Ushakov, I. A., "An Algorithm for Checking the Connectivity of a Graph", Iev. AU.Tckh.Kib., No. 4, 85-86,1967 Trans: Eng. Cyb., No. 4, 82-83, 1967
• 21: Berge, Claude, Theory of Graphs, 152-155, 1962, Wiley
• 22: Berge, Claude and Ghouila-Houri, A., Programming Games, and Transportation Networks, 177-182
• 23: Seppanen, Jouko J., "Spanning Tree (H)" Algorithm 399, Comm. ACM, 13, No.10, October, 1970
• 24: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 25: Read, Ronald C., "Teaching Graph Theory to Computer," in Recent Progress Combinatorics, W. T. Tutte (ed) Academic 1969
• 26: Johnson, Ellis, Personal Communication, 1972.
• 27: London, Ralph L., "Certification of Algorithm 245(M1) Treesorts", Certification of Algorithm 245, ACM Collected Algorithms, 1970.

INDEX TERMS

Keywords:
connectivity, minimum spanning trees, sorting