Spy-game on graphs: complexity and simple topologies
DOI10.1016/j.tcs.2017.11.015zbMath1394.91051OpenAlexW2594691417MaRDI QIDQ1748987
Stéphane Pérennes, Nícolas A. Martins, Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Rudini Menezes Sampaio
Publication date: 15 May 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01782246/file/Spygames1.pdf
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Cops and robbers from a distance
- On a generalization of Meyniel's conjecture on the Cops and Robbers game
- Cops and robber game without recharging
- A game of cops and robbers
- Vertex-to-vertex pursuit in a graph
- Cops and robbers is EXPTIME-complete
- Pursuing a fast robber on a graph
- Graphs with equal eternal vertex cover and eternal domination numbers
- Catching a fast robber on the grid
- Tight bounds for eternal dominating sets in graphs
- Patrolling Games
- Cops and Robber with Constraints
- Algorithmic construction of sets for k -restrictions
- Patrolling a Border
- Cop and Robber Games When the Robber Can Hide and Ride
This page was built for publication: Spy-game on graphs: complexity and simple topologies