Algorithm 422: minimal spanning tree [H]
- 1 April 1972
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 15 (4) , 273-274
- https://doi.org/10.1145/361284.361299
Abstract
This algorithm generates a spanning tree of minimal total edge length for an undirected graph specified by an array of inter-node edge lengths using a technique suggested by Dijkstra [1]. Execution time is proportional to the square of the number of nodes of the graph; a minimal spanning tree for a graph of 50 nodes is generated in 0.1 seconds on an IBM System 360/67. Previous algorithms [2, 3, 4, 5] require an amount of computation which depends on the graph topology and edge lengths and are best suited to graphs with few edges.Keywords
This publication has 5 references indexed in Scilit:
- Matrix computations with Fortran and pagingCommunications of the ACM, 1972
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- Formal Procedures for Connecting Terminals with a Minimum Total Wire LengthJournal of the ACM, 1957
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956