Euclidean bounded-degree spanning tree ratios
From MaRDI portal
Publication:1762944
DOI10.1007/s00454-004-1117-3zbMath1066.68092OpenAlexW2002985966MaRDI QIDQ1762944
Publication date: 11 February 2005
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-004-1117-3
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ Polynomial area bounds for MST embeddings of trees ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ The complexity of symmetric connectivity in directional wireless sensor networks ⋮ Degree-bounded minimum spanning trees ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ Degree-bounded minimum spanning tree for unit disk graph ⋮ Bounded-angle minimum spanning trees ⋮ A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST
