Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420268 | Discrete Applied Mathematics | 2010 | 7 Pages |
Abstract
We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an nn-dimensional grid, at least nn cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which nn cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal,