A cops and robber game in multidimensional grids |
| |
Authors: | Sayan Bhattacharya Swagato Sanyal |
| |
Institution: | a Department of Computer Science, Duke University, Durham, NC 27708, USAb Department of Computer Science and Engineering, Jadavpur University, Kolkata 700 032, Indiac Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur 208 016, India |
| |
Abstract: | We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an n-dimensional grid, at least n 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 n 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. |
| |
Keywords: | Cops and robber Game Graph Grid Winning strategy |
本文献已被 ScienceDirect 等数据库收录! |
|