The guarding problem -- complexity and approximation

DOI10.1007/978-3-642-10217-2_45MaRDI QIDQ3651572zbMATH OpenOpenAlexFDO

Authors T. V. Thirumala Reddy, D. Sai Krishna, C. Pandu Rangan

Publication date 11 December 2009

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-10217-2_45

zbMATH Keywords

approximation algorithmscops regionPSPACE-completeQBFQSATquantified Boolean formula)quantified satisfiabilityrobber region

Mathematics Subject Classification ID

Graph designs and isomorphic decomposition (05C51) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• How to guard a graph?
• How to Guard a Graph?
• Complexity of the cop and robber guarding game
• The guarding game is E-complete
• Cop-robber guarding game with cycle robber-region

Cited in

(16)

• An efficient algorithm for the three-guard problem
• A heuristic approach to the overnight security service problem
• Guarding a subgraph as a tool in pursuit-evasion games
• How to guard a graph against tree moves
• Complexity of the cop and robber guarding game
• On Some City Guarding Problems
• Guard games on graphs: keep the intruder out!
• The guarding game is E-complete
• scientific article; zbMATH DE number 2080273 (Why is no real title available?)
• Cop-Robber Guarding Game with Cycle Robber Region
• Optimal Guard Placement Problem Under L-Visibility
• Algorithms and Computation
• Guard games on graphs: keep the intruder out!
• How to guard a graph?
• Computational complexity of the police officer patrol problem on weighted digraphs
• Romeo and juliet is ExpTime-complete

This page was built for publication: The guarding problem -- complexity and approximation

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