Minimum Spanning Trees in k-Dimensional Space
Author:
- Pravin M. VaidyaPVPravin M. Vaidya
- 1 June 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (3) , 572-582
Abstract
We study the problem of finding a minimum spanning tree in the complete graph on a set V of n points in k-dimensional space. The points are the vertices of this graph and the weight of an edge between two points is the distance between the points under some $L_q $ metric. We give an $O(\varepsilon ^{ - k} n\log n)$ algorithm for finding an approximate minimum spanning tree in such a graph; the weight of the approximate minimum spanning tree is guaranteed to be at most $(1 + \varepsilon )$ times the weight of a minimum spanning tree. We also present an algorithm to find a minimum spanning tree in the complete graph on V. Under the assumption that V consists of n random points, independently and uniformly distributed in the unit k-cube $[0,1]^k $, the expected running time of this minimum spanning tree algorithm is shown to be $O(n\alpha (cn,n))$ where c is a constant dependent on k and $\alpha $ is the inverse Ackermann function.
Keywords
This publication has 12 references indexed in Scilit:
- A Fast Approximation Algorithm For Minimum Spanning Trees In K-Dimensional Space1984
- Efficient Implementation Of Graph Algorithms Using Contraction1984
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related ProblemsSIAM Journal on Computing, 1982
- Finding Minimum Spanning TreesSIAM Journal on Computing, 1976
- Closest-point problems1975
- An 0(|E|loglog|V|) algorithm for finding minimum spanning treesInformation Processing Letters, 1975
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Graph-Theoretical Methods for Detecting and Describing Gestalt ClustersIEEE Transactions on Computers, 1971
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956