Catching a fast robber on the grid

DOI10.1016/J.JCTA.2017.06.009MaRDI QIDQ2401986zbMATH OpenOpenAlexFDO

Authors Amy Shaw, Béla Bollobás, Paul Balister, Bhargav P. Narayanan

Publication date 5 September 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

cops and robbersgames on graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that when the speed of the robber is a sufficiently large constant, the number of cops needed to catch the robber on an $nimesn$ grid is $exp(Omega(logn/loglogn))$.

Recommendations

• Catching an infinitely fast robber on a grid
• Fast Robber in Planar Graphs
• A cops and robber game in multidimensional grids
• Pursuing a fast robber on a graph
• Lower bounds for the cop number when the robber is fast

Cites work

• A bound for the cops and robbers problem
• Conway's Angel in three dimensions
• Fast Robber in Planar Graphs
• Lower bounds for the cop number when the robber is fast
• Meyniel's conjecture on the cop number: a survey
• On a game of policemen and robber
• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• On Meyniel's conjecture of the cop number
• Pursuing a fast robber on a graph
• The angel and the devil in three dimensions
• The Angel Game in the Plane
• The Angel of Power 2 Wins
• Variations on cops and robbers
• Vertex-to-vertex pursuit in a graph

Cited in

(15)

• Some pursuit-evasion problems on grids
• Spy-game on graphs: complexity and simple topologies
• Study of a combinatorial game in graphs through linear programming
• Capture times in the bridge-burning cops and robbers game
• Catching an infinitely fast robber on a grid
• Locating a backtracking robber on a tree
• Spy game: FPT-algorithm, hardness and graph products
• Spy game: FPT-algorithm and results on graph products
• Fast Robber in Planar Graphs
• Connected Search for a Lazy Robber
• Connected search for a lazy robber
• Cops and robber on butterflies, grids, and AT-free graphs
• Parameterized analysis of the cops and robber problem
• A covering pursuit game
• Cops and robber on butterflies and solid grids

This page was built for publication: Catching a fast robber on the grid

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