Lucas Cardoso Pereira

Lucas Cardoso Pereira

he/him

CS undergraduate student @ State University of Campinas
Member of the Laboratory of Optimization and Combinatorics (LOCo)

Sitemap

A list of all the posts and pages found on the site. For you robots out there, there is an XML version available for digesting as well.

Pages

Posts

portfolio

publications

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: <a href=https://doi.org/10.5753/etc.2026.23745>https://doi.org/10.5753/etc.2026.23745</a>.
Download Paper | Download Slides | Download Bibtex

talks

teaching

Teaching experience 1

Undergraduate course, University 1, Department, 2014

This is a description of a teaching experience. You can use markdown like any other post.

Teaching experience 2

Workshop, University 1, Department, 2015

This is a description of a teaching experience. You can use markdown like any other post.