SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES

DOI10.1142/S0218195913500052MaRDI QIDQ3459364zbMATH OpenOpenAlexFDO

Authors Changryeol Lee, Otfried Cheong

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

dilationgeometric networkminimum spanning treesingle sourcespanner

Mathematics Subject Classification ID

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

Abstract: Given a set $S$ of points in the plane, a geometric network for $S$ is a graph $G$ with vertex set $S$ and straight edges. We consider a broadcasting situation, where one point $rinS$ is a designated source. Given a dilation factor $delta$, we ask for a geometric network $G$ such that for every point $vinS$ there is a path from $r$ to $v$ in $G$ of length at most $delta|rv|$, and such that the total edge length is minimized. We show that finding such a network of minimum total edge length is NP-hard, and give an approximation algorithm.

Recommendations

• Degree-bounded minimum spanning trees
• scientific article; zbMATH DE number 91018
• Minimum Diameter Spanning Trees and Related Problems
• Approximating minimum bounded degree spanning trees to within one of optimal
• Minimum bottleneck spanning trees with degree bounds
• Minimum spanning trees in d dimensions
• scientific article; zbMATH DE number 1436136
• Computing minimum dilation spanning trees in geometric graphs
• Approximating the degree-bounded minimum diameter spanning tree problem
• Approximating the degree-bounded minimum diameter spanning tree problem

Cites work

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

Cited in

(5)

• Light orthogonal networks with constant geometric dilation
• Computing minimum dilation spanning trees in geometric graphs
• Computing geometric minimum-dilation graphs is NP-hard
• A PTAS for k-hop MST on the Euclidean plane: improving dependency on k
• Computing a minimum-dilation spanning tree is NP-hard

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459364)