TY - JOUR
AU - Akitaya, Hugo
AU - Biniaz, Ahmad
AU - Bose, Prosenjit
AU - De Carufel, Jean-Lou
AU - Maheshwari, Anil
AU - da Silveira, Luís Fernando Schultz Xavier
AU - Smid, Michiel
PY - 2023/01/01
Y2 - 2024/10/05
TI - The Minimum Moving Spanning Tree Problem
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 27
IS - 1
SE -
DO - 10.7155/jgaa.00607
UR - https://jgaa.info/index.php/jgaa/article/view/paper607
SP - 1-18
AB - We investigate the problem of finding a spanning tree of a set of $n$ moving points in $\mathbb{R}^{\dim}$ that minimizes the maximum total weight (under any convex distance function) or the maximum bottleneck throughout the motion.The output is a single tree, i.e., it does not change combinatorially during the movement of the points.We call these trees a minimum moving spanning tree, and a minimum bottleneck moving spanning tree, respectively.We show that, although finding the minimum bottleneck moving spanning tree can be done in $O(n^2)$ time when $\dim$ is a constant, it is NP-hard to compute the minimum moving spanning tree even for $\dim=2$.We provide a simple $O(n^2)$-time 2-approximation and a $O(n \log n)$-time $(2+\varepsilon)$-approximation for the latter problem, for any constant $\dim$ and any constant $\varepsilon>0$.
ER -