Lucas de Oliveira Silva

dblp:338/6880 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2025
0000-0002-7846-5903ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2025 Realizing Graphs with Cut Constraints
Vítor Gomes Chagas, Samuel Plaça de Paula, Greis Y. O. Quesquén, Lucas de Oliveira Silva, Uéverton S. Souza
CIAC (1)4
2023 Freeze-Tag is NP-hard in 3D with L1 distance
abstract
The Freeze-Tag Problem (FTP) is the task of scheduling the activation of a robot swarm. The input consists of the initial locations of a set of mobile robots in some metric space. A single robot is initially “active” while the others are initially “frozen”. Active robots can move at unit speed, and upon reaching the location of a frozen robot, the latter is activated. The goal is to activate all the robots within the minimum time, minimizing the so-called makespan of the schedule. The complexity of this problem in Euclidean spaces was open until 2017, when Abel et al. [1] proved that FTP is NP-hard in the Euclidean plane with L2 distance. During that same year, Demaine and Rudoy [2] showed that it is also NP-hard in 3D Euclidean space with Lp distance for any p > 1, but left open the case with p = 1. This paper closes this gap and shows that FTP is indeed NP-hard in 3D Euclidean space with L1 distance. Furthermore, the hardness result holds in the strong sense, such that every coordinate is a rational bounded by a polynomial in the instance size.
Lehilton L. C. Pedrosa, Lucas de Oliveira Silva
LAGOS2