Complexity of the cop and robber guarding game

DOI10.1007/978-3-642-25011-8_29MaRDI QIDQ3111664zbMATH OpenOpenAlexFDO

Authors Robert Šámal, Rudolf Stolař, T. Valla

Publication date 13 January 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25011-8_29

zbMATH Keywords

computational complexitycops and robber gameE-completenessgraph guarding gamepursuit game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Recommendations

• The guarding game is E-complete
• How to guard a graph?
• How to Guard a Graph?
• The guarding problem -- complexity and approximation
• Cop-robber guarding game with cycle robber-region

Cited in

(10)

• Spy-game on graphs: complexity and simple topologies
• Guarding a subgraph as a tool in pursuit-evasion games
• How to guard a graph against tree moves
• Guard games on graphs: keep the intruder out!
• The guarding problem -- complexity and approximation
• The guarding game is E-complete
• Cop-Robber Guarding Game with Cycle Robber Region
• How to guard a graph?
• Romeo and juliet is ExpTime-complete
• The complexity of zero-visibility cops and robber

This page was built for publication: Complexity of the cop and robber guarding game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3111664)