| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875520 | Theoretical Computer Science | 2018 | 15 Pages |
Abstract
We consider the computational complexity of the problem, showing that it is NP-hard (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nathann Cohen, NÃcolas A. Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, Rudini Sampaio,