Placement of charging stations for energy-constrained robots in spider graphs - Pereira, Lucas Cardoso; Ravelo, Santiago Valdés (Anais do Encontro de Teoria da Computação (ETC), 2026)
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 ⊆ V , and a set of target vertices T ⊆ V , with |S| = |T| = 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 O(|V|)-time algorithm, and presents a more general linear-time solution for spider graphs, achieving O(|V|) time complexity.