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

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)