Cop and Robber Games When the Robber Can Hide and Ride

DOI10.1137/100784035zbMath1228.05213arXiv1001.4457OpenAlexW2092730474MaRDI QIDQ3094914

Jérémie Chalopin, Yann Vaxès, Victor Chepoi, Nicolas Nisse

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.4457

zbMATH Keywords

cop-win graphs\(\delta\)-hyperbolicitycop and robber gamesdismantling orderingsdismantling scheme

Mathematics Subject Classification ID

2-person games (91A05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (16)

General cops and robbers games with randomness ⋮ Data center interconnection networks are not hyperbolic ⋮ A probabilistic version of the game of zombies and survivors on graphs ⋮ Pursuit evasion on infinite graphs ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ A cop-winning strategy on strongly cop-win graphs ⋮ Coarse geometry of the cops and robber game ⋮ Cops and robber on butterflies, grids, and AT-free graphs ⋮ Spy game: FPT-algorithm and results on graph products ⋮ To satisfy impatient web surfers is hard ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Spy-game on graphs: complexity and simple topologies ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ A survey on the relationship between the game of cops and robbers and other game representations ⋮ Cops, a fast robber and defensive domination on interval graphs ⋮ Control Sequencing in a Game of Identity Pursuit-Evasion

This page was built for publication: Cop and Robber Games When the Robber Can Hide and Ride