Minimum Spanning Trees in k-Dimensional Space

DOI10.1137/0217035zbMath0652.68083OpenAlexW1992843866MaRDI QIDQ3798263

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)

Related Items

On the Steiner ratio in 3-space ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ Minimal length tree networks on the unit sphere ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ Well-separated pair decomposition in linear time? ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Region-fault tolerant geometric spanners ⋮ Dynamic smooth compressed quadtrees