On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

Details On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

2009-09-08

arxiv.org/abs/0909.1381v1

Computer Science

Discrete Mathematics

This is a revised and extended version of the poster paper with the same title that has been presented in the 8th Asian Sympos

Scientific paper

We theoretically analyze the Cops and Robber Game for the first time in a multidimensional grid. It is shown that for an $n$-dimensional grid, at least $n$ cops are necessary to ensure capture of the robber. We also present a set of cop strategies for which $n$ 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.

Affiliated with

Also associated with

No associations

Rating

On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107659