On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
arXiv:0909.1381 · doi:10.1016/j.dam.2010.06.014
Abstract
We theoretically analyze the Cops and Robber Game for the first time in a multidimensional grid. It is shown that for an -dimensional grid, at least cops are necessary to ensure capture of the robber. We also present a set of cop strategies for which cops are provably sufficient to catch the robber. Further, for two-dimensional grid, we provide an efficient cop strategy for which the robber is caught even by a single cop under certain conditions.
This is a revised and extended version of the poster paper with the same title that has been presented in the 8th Asian Symposium on Computer Mathematics (ASCM), December 15-17, 2007, Singapore