Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces
- 1 February 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (2), 97-105
- https://doi.org/10.1109/tc.1978.1675043
Abstract
Algorithms are presented that construct the shortest connecting network, or minimal spanning tree (MST), of N points embedded in k-dimensional coordinate space. These algorithms take advantage of the geometry of such spaces to substantially reduce the computation from that required to construct MST's of more general graphs. An algorithm is also presented that constructs a spanning tree that is very nearly minimal with computation proportional to N log N for all k.This publication has 12 references indexed in Scilit:
- A hardware wrapper for the SHA-3 hash algorithmsPublished by Institution of Engineering and Technology (IET) ,2010
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977
- An 0(|E|loglog|V|) algorithm for finding minimum spanning treesInformation Processing Letters, 1975
- Algorithm 422: minimal spanning tree [H]Communications of the ACM, 1972
- Graph-Theoretical Methods for Detecting and Describing Gestalt ClustersIEEE Transactions on Computers, 1971
- Minimum Spanning Trees and Single Linkage Cluster AnalysisJournal of the Royal Statistical Society Series C: Applied Statistics, 1969
- Hierarchical clustering schemesPsychometrika, 1967
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- 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