How to guard a graph?
From MaRDI portal
Publication:652526
DOI10.1007/s00453-009-9382-4zbMath1233.91047OpenAlexW2054503448WikidataQ60488568 ScholiaQ60488568MaRDI QIDQ652526
Alex Hall, Matúš Mihalák, Elias Vicari, Fedor V. Fomin, Peter Widmayer, Petr A. Golovach
Publication date: 14 December 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9382-4
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57)
Related Items (5)
The guarding game is E-complete ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ How to guard a graph against tree moves ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Guarding a subgraph as a tool in pursuit-evasion games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of pursuit on a graph
- A game of cops and robbers
- An annotated bibliography on guaranteed graph searching
- On the cop number of a graph
- Maximum independent set and maximum clique algorithms for overlap graphs
- Some results about pursuit games on metric spaces obtained through graph theory techniques
- Vertex-to-vertex pursuit in a graph
- A note on \(k\)-cop, \(l\)-robber games on graphs
- Normal hypergraphs and the perfect graph conjecture
- The Guarding Problem – Complexity and Approximation
- On Path Cover Problems in Digraphs and Applications to Program Testing
- Graph Classes: A Survey
- On the hardness of approximating minimization problems
- Cop-Robber Guarding Game with Cycle Robber Region
This page was built for publication: How to guard a graph?
