Title: Cops and robber on grids and tori,
Abstract: This paper is a contribution to the classical cops and robber problem on a
graph, directed to two-dimensional grids and toroidal grids. These studies are
generally aimed at determining the minimum number of cops needed to capture the
robber and proposing algorithms for the capture. We apply some new concepts to
propose a new solution to the problem on grids that was already solved under a
different approach, and apply these concepts to give efficient algorithms for
the capture on toroidal grids. As for grids, we show that two cops suffice even
in a semi-torus (i.e. a grid with toroidal closure in one dimension) and three
cops are necessary and sufficient in a torus. Then we treat the problem in
function of any number k of cops, giving efficient algorithms for grids and
tori and computing lower and upper bounds on the capture time. Conversely we
determine the minimum value of k needed for any given capture time and study a
possible speed-up phenomenon.