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

zbMATH Keywords

graphscops and robber gamesPSPACE-hard

Mathematics Subject Classification ID

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

Eternal domination: \(D\)-dimensional Cartesian and strong grids and everything in between ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Eternal distance-\(k\) domination on graphs ⋮ Spy game: FPT-algorithm and results on graph products ⋮ Study of a combinatorial game in graphs through linear programming ⋮ The game of cops and eternal robbers

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