VLDB 2026 Research / reviewers in the wild / expert
Lucas de Oliveira Silva
dblp:338/6880
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 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 distanceabstractThe 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 |
LAGOS | 2 |