Placement of charging stations for energy-constrained robots in spider graphs
Published in Anais do XI Encontro de Teoria da Computação, 2026
Abstract: In the MIN-STATION problem, we are given a simple graph \(G=(V,E)\), a set of \(m\) robots initially positioned on vertices in \(S \subseteq V\), and a set of target vertices \(T \subseteq V\), with \(\lvert S \rvert = \lvert T \rvert = m\), along with a positive integer \(r\). The goal is to determine the minimum number of charging stations to place on the vertices so that each robot can move from a distinct vertex in \(S\) to a distinct vertex in \(T\) without running out of energy, given that each robot can traverse at most \(r\) edges between consecutive recharges. This work reviews existing results in the literature for paths, which admit an \(\mathcal{O}(\lvert V \rvert)\)-time algorithm, and presents a more general linear-time solution for spider graphs, achieving \(\mathcal{O}(\lvert V \rvert)\) time complexity.
Recommended citation: L. Pereira and S. Ravelo. "Placement of charging stations for energy-constrained robots in spider graphs", in Anais do XI Encontro de Teoria da Computação, Gramado/RS, 2026, pp. 220-224, doi: https://doi.org/10.5753/etc.2026.23745.
Download Paper | Download Slides | Download Bibtex