Cops and robbers from a distance

DOI10.1016/j.tcs.2010.07.003zbMath1200.91042OpenAlexW1980595063MaRDI QIDQ604465

Ehsan Chiniforooshan, Anthony Bonato, Paweł Prałat

Publication date: 11 November 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.07.003

zbMATH Keywords

polynomial time algorithmgraphsNP-hardrandom graphstrong productcop number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (23)

Variations on cops and robbers ⋮ On Meyniel's conjecture of the cop number ⋮ A probabilistic version of the game of zombies and survivors on graphs ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ An Introduction to Lazy Cops and Robbers on Graphs ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Cops and Robber game with a fast robber on expander graphs and random graphs ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ Coarse geometry of the cops and robber game ⋮ Characterizations of \(k\)-copwin graphs ⋮ Lazy Cops and Robbers on Hypercubes ⋮ Spy game: FPT-algorithm and results on graph products ⋮ To satisfy impatient web surfers is hard ⋮ The fast robber on interval and chordal graphs ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Spy-game on graphs: complexity and simple topologies ⋮ A survey on the relationship between the game of cops and robbers and other game representations ⋮ 4-cop-win graphs have at least 19 vertices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cops, a fast robber and defensive domination on interval graphs ⋮ Conjectures on Cops and Robbers ⋮ Containment game played on random graphs: another zig-zag theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of pursuit on a graph
• Retracts of strong products of graphs
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Cops and robbers in graphs with large girth and Cayley graphs
• On bridged graphs and cop-win graphs
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• Pursuing a fast robber on a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• Chasing robbers on random graphs: Zigzag theorem
• Pursuit-Evasion in Models of Complex Networks
• A Bound for the Cops and Robbers Problem
• A better bound for the cop number of general graphs

This page was built for publication: Cops and robbers from a distance