Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00607
The Minimum Moving Spanning Tree Problem
Hugo A. Akitaya,
Ahmad Biniaz,
Prosenjit Bose,
Jean-Lou De Carufel,
Anil Maheshwari,
Luís Fernando Schultz Xavier da Silveira, and
Michiel Smid
Vol. 27, no. 1, pp. 1-18, 2023. Regular paper.
Abstract 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$.
This work is licensed under the terms of the CC-BY license.
|
Submitted: June 2021.
Reviewed: July 2022.
Revised: September 2022.
Accepted: October 2022.
Final: November 2022.
Published: January 2023.
Communicated by
Csaba D. Tóth
|
Journal Supporters
|