How to guard a graph?

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

zbMATH Keywords

complexityalgorithmsapproximationwinning strategygame of cops and robbersguarding of vertices

Mathematics Subject Classification ID

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?