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,
JeanLou De Carufel,
Anil Maheshwari,
Luís Fernando Schultz Xavier da Silveira, and
Michiel Smid
Vol. 27, no. 1, pp. 118, 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 NPhard to compute the minimum moving spanning tree even for $\dim=2$.
We provide a simple $O(n^2)$time 2approximation 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 CCBY 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
