Minimum Spanning Trees in k-Dimensional Space

DOI10.1137/0217035MaRDI QIDQ3798263zbMATH OpenOpenAlexFDO

Authors Pravin M. Vaidya

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217035

zbMATH Keywords

minimum spanning treeapproximation algorithmscomplete graphinverse Ackermann function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum spanning trees in d dimensions
• scientific article; zbMATH DE number 1436136
• Minimum spanning hypertrees
• Minimum Diameter Spanning Trees and Related Problems
• Minimum spanning trees
• Minimal spanning trees
• On constructing minimum spanning trees in \(R_ 1^ k\)
• Degree-bounded minimum spanning trees
• An algorithm for \(k^{\text{th}}\) minimum spanning tree

Cited in

(32)

• On the Steiner ratio in 3-space
• The minimal spanning tree and the upper box dimension
• Dynamic smooth compressed quadtrees
• A low arithmetic-degree algorithm for computing proximity graphs
• Structural Information and Communication Complexity
• Minimal spanning trees and Stein's method
• Well-separated pair decomposition in linear time?
• Stochastic minimum spanning trees in Euclidean spaces
• Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
• Region-fault tolerant geometric spanners
• scientific article; zbMATH DE number 7478573 (Why is no real title available?)
• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Transitions in geometric minimum spanning trees
• Minimum spanning trees in \(d\) dimensions
• Approximating \(k\)-hop minimum-spanning trees
• Fast geometric approximation techniques and geometric embedding problems
• An algorithm for geometric minimum spanning trees requiring nearly linear expected time
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• On a proposed divide-and-conquer minimal spanning tree algorithm
• Degree bounded bottleneck spanning trees in three dimensions
• Minimal length tree networks on the unit sphere
• A fast minimum spanning tree algorithm based on \(K\)-means
• scientific article; zbMATH DE number 1512690 (Why is no real title available?)
• Approximating all-points furthest pairs and maximum spanning trees in metric spaces
• Euclidean minimum spanning trees and bichromatic closest pairs
• Minimum-sum dipolar spanning tree in \(\mathbb R^3\)
• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• Geometric minimum spanning trees via well-separated pair decompositions
• Approximate minimum weight matching on points in k-dimensional space
• The Filter-Kruskal Minimum Spanning Tree Algorithm
• scientific article; zbMATH DE number 3978859 (Why is no real title available?)

This page was built for publication: Minimum Spanning Trees in k-Dimensional Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798263)