The Guarding Problem – Complexity and Approximation

DOI10.1007/978-3-642-10217-2_45zbMath1267.05198OpenAlexW1519653974MaRDI QIDQ3651572

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

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 algorithmsPSPACE-completeQBFQSATquantified satisfiabilitycops regionquantified Boolean formula)robber region

Mathematics Subject Classification ID

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

Related Items (5)

The guarding game is E-complete ⋮ How to guard a graph against tree moves ⋮ Guard games on graphs: keep the intruder out! ⋮ How to guard a graph? ⋮ Guarding a subgraph as a tool in pursuit-evasion games

This page was built for publication: The Guarding Problem – Complexity and Approximation