The guarding game is E-complete
From MaRDI portal
Publication:389949
DOI10.1016/j.tcs.2013.11.034zbMath1307.91043arXiv1112.6140OpenAlexW2080925544WikidataQ105337610 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 complexitycops-and-robber gamepursuit gameE-completenessgames on propositional formulasgraph guarding game
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)
Related Items (3)
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The guarding game is E-complete
