The guarding game is E-complete

DOI10.1016/j.tcs.2013.11.034zbMath1307.91043arXiv1112.6140OpenAlexW2080925544WikidataQ105337610 ScholiaQ105337610MaRDI QIDQ389949

Tomáš Valla, Robert Šámal

Publication date: 22 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.6140

zbMATH Keywords

computational complexitycops-and-robber gamepursuit gameE-completenessgames on propositional formulasgraph guarding game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Related Items

Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Guarding a subgraph as a tool in pursuit-evasion games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cop-robber guarding game with cycle robber-region
• Guard games on graphs: keep the intruder out!
• How to guard a graph?
• The complexity of pursuit on a graph
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Comparing complexity classes
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• Vertex-to-vertex pursuit in a graph
• On the computational complexity of a game of cops and robbers
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• Eternally secure sets, independence sets and cliques
• Tight bounds for eternal dominating sets in graphs
• Complexity of the Cop and Robber Guarding Game
• The Guarding Problem – Complexity and Approximation
• Provably Difficult Combinatorial Games