IEEE Transactions on Computers · 1978 · 120 citations · 18 references
ComputingComputer ScienceComputational GeometryData StructuresGeometric ModelingGeometric GraphsGraph AlgorithmsGraph TheoryNetwork TopologyRandomized Geometric AlgorithmsShortest Path AlgorithmsCoordinate Geometry Of SpaceMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ConstructionMinimum Spanning Tree ProblemShortest PathsSpanning Tree ConstructionTree Algorithms
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.
18
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Hierarchical Clustering Schemes
S. C. Johnson · Psychometrika · 1967 · 4.9K citations