Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces
IEEE Transactions on ComputersPublished 1 February 1978
Bentley, Friedman
Citations119
SJR quartileQ1
SJR score1.16
SNIP1.61
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Algorithms are presented that construct the shortest connecting network, or minimal spanning tree, of N points embedded in k-dimensional coordinate space and 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.
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.
Keywords
Computer Science
Proceedings of the American Mathematical SocietyOn the shortest spanning subtree of a graph and the traveling salesman problem
5,003 Citations1956Joseph B. Kruskal
PsychometrikaHierarchical Clustering Schemes
4,891 Citations1967S. C. Johnson
A useful correspondence is developed between any hierarchical system of such clusters, and a particular type of distance measure, that gives rise to two methods of clustering that are computationally rapid and invariant under monotonic transformations of the data.
Bell System Technical JournalShortest Connection Networks And Some Generalizations
4,498 Citations1957R. C. Prim
Simple and practical procedures are given for solving the basic problem of interconnecting a given set of terminals with the shortest possible network of direct links both graphically and computationally.
ACM Transactions on Mathematical SoftwareAn Algorithm for Finding Best Matches in Logarithmic Expected Time
2,765 Citations1977Jerome H. Friedman, Jon Bentley +1 more
IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters
1,741 Citations1971C. T. Zahn
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.
Journal of the Royal Statistical Society Series C (Applied Statistics)Minimum Spanning Trees and Single Linkage Cluster Analysis
1,233 Citations1969J. C. Gower, G. J. Ross
Minimum spanning trees (MST) and single linkage cluster analysis (SLCA) are explained and it is shown that all the information required for the SLCA of a set of points is contained in their MST.
Information Processing LettersAn 0(|E|loglog|V|) algorithm for finding minimum spanning trees
159 Citations1975Andrew Chi-Chih Yao
The algorithm is a modification of an algorithm by SoWn that works by successively enlarging, components al the MST, by shrinking each group of vertices to node, to obtain a new graph with at most odes.
IEEE Transactions on ComputersA Triangulation Method for the Sequential Mapping of Points from N-Space to Two-Space
146 Citations1977Lee, Slagle +1 more
A method for the sequential mapping of points in a high-dimensional space onto a plane is presented, where whenever a new point is mapped, its distgnces to two points previously mapped are exactly preserved.
Journal of the ACMFormal Procedures for Connecting Terminals with a Minimum Total Wire Length
70 Citations1957H. Loberman, A. Weinberger
Two methods for systematically selecting the shortest connections from a list of possible connections to obtain a minimum total wire length are presented, which will be called a minimum tree.
Communications of the ACMAlgorithm 422: minimal spanning tree [H]
59 Citations1972V. Kevin M. Whitney
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].
A hardware wrapper for the SHA-3 hash algorithms
54 Citations2010Brian Baldwin, Andrew W. Byrne +5 more
A hardware wrapper interface is presented which attempts to encompass all the competition entries (and indeed, hash algorithms in general) across any number of both FPGA and ASIC hardware platforms, and attempts to standardise the hashing algorithms to allow accurate and fair area, timing and power measurement between the different designs.
IEEE Transactions on ComputersA Note on Minimal Reed-Muller Canonical Forms of Switching Functions
14 Citations1977Kodandapani, Setlur
It is shown that the task of obtaining minimal RMC forms is simplified in the case of symmetric functions and self-dual functions.
SpringerBriefs in computer scienceComputational Geometry
4 Citations2013Michal Forišek, Monika Steinová