How to guard a graph?

DOI10.1007/S00453-009-9382-4MaRDI QIDQ652526zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Petr A. Golovach, Alex Hall, Matúš Mihalák, E. Vicari, Peter Widmayer

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

algorithmsapproximationcomplexitygame of cops and robbersguarding of verticeswinning strategy

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Recommendations

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

Cites work

• A game of cops and robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• An annotated bibliography on guaranteed graph searching
• Chases and escapes. The mathematics of pursuit and evasion
• Cop-Robber Guarding Game with Cycle Robber Region
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 3204219 (Why is no real title available?)
• scientific article; zbMATH DE number 3407692 (Why is no real title available?)
• Maximum independent set and maximum clique algorithms for overlap graphs
• Normal hypergraphs and the perfect graph conjecture
• On Path Cover Problems in Digraphs and Applications to Program Testing
• On the cop number of a graph
• On the hardness of approximating minimization problems
• Searching and sweeping graphs: a brief survey
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• The complexity of pursuit on a graph
• The guarding problem -- complexity and approximation
• Vertex-to-vertex pursuit in a graph

Cited in

(12)

• Guarding a subgraph as a tool in pursuit-evasion games
• How to guard a graph against tree moves
• Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
• Complexity of the cop and robber guarding game
• Guard games on graphs: keep the intruder out!
• How to Guard a Graph?
• The guarding problem -- complexity and approximation
• The guarding game is E-complete
• Cop-Robber Guarding Game with Cycle Robber Region
• Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
• Guard games on graphs: keep the intruder out!
• Romeo and juliet is ExpTime-complete

This page was built for publication: How to guard a graph?

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