The guarding game is E-complete
From MaRDI portal
Publication:389949
DOI10.1016/j.tcs.2013.11.034zbMath1307.91043arXiv1112.6140WikidataQ105337610 ScholiaQ105337610MaRDI QIDQ389949
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
computational complexity; cops-and-robber game; pursuit game; E-completeness; games on propositional formulas; graph guarding game
68Q25: Analysis of algorithms and problem complexity
91A43: Games involving graphs
91A24: Positional games (pursuit and evasion, etc.)
Related Items
Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Guarding a subgraph as a tool in pursuit-evasion games, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
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
