Posts by Collection

Portfolio item number 1

Short description of portfolio item number 1

Portfolio item number 2

Short description of portfolio item number 2

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