SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES

DOI10.1142/S0218195913500052zbMath1344.68256arXiv1206.6943OpenAlexW2037501392MaRDI QIDQ3459364

Changryeol Lee, Otfried Schwarzkopf

Publication date: 22 December 2015

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.6943

zbMATH Keywords

dilationminimum spanning treegeometric networkspannersingle source

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Minimum dilation stars
• Computing a minimum-dilation spanning tree is NP-hard
• Approximating \(k\)-hop minimum-spanning trees
• COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD
• ON SPANNERS OF GEOMETRIC GRAPHS
• Constructing minimal spanning/Steiner trees with bounded path length

This page was built for publication: SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES