Minimum Spanning Trees in k-Dimensional Space

DOI10.1137/0217035zbMATH Open0652.68083OpenAlexW1992843866MaRDI QIDQ3798263FDOQ3798263

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

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

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)

Cited In (31)

• On the Steiner ratio in 3-space
• Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
• The Filter-Kruskal Minimum Spanning Tree Algorithm
• Fast geometric approximation techniques and geometric embedding problems
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Approximating \(k\)-hop minimum-spanning trees
• An algorithm for geometric minimum spanning trees requiring nearly linear expected time
• Title not available (Why is that?)
• 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
• Stochastic minimum spanning trees in Euclidean spaces
• Region-fault tolerant geometric spanners
• Minimal length tree networks on the unit sphere
• 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
• A low arithmetic-degree algorithm for computing proximity graphs
• Minimum spanning trees in \(d\) dimensions
• Title not available (Why is that?)
• Euclidean minimum spanning trees and bichromatic closest pairs
• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Degree bounded bottleneck spanning trees in three dimensions
• Minimal spanning trees and Stein's method
• Well-separated pair decomposition in linear time?
• Title not available (Why is that?)
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Geometric minimum spanning trees via well-separated pair decompositions
• A fast minimum spanning tree algorithm based on \(K\)-means

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)