Catching an infinitely fast robber on a grid
| Autor: | William B. Kinnersley, Nikolas Townsend |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer Science::Robotics
FOS: Computer and information sciences Quantitative Biology::Neurons and Cognition Discrete Mathematics (cs.DM) Computer Science::Discrete Mathematics Applied Mathematics Physics::Medical Physics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Computer Science::Human-Computer Interaction Combinatorics (math.CO) Computer Science - Discrete Mathematics |
| DOI: | 10.48550/arxiv.2107.14193 |
| Popis: | We consider a variant of Cops and Robbers in which the robber may traverse as many edges as he likes in each turn, with the constraint that he cannot pass through any vertex occupied by a cop. We study this model on several classes of grid-like graphs. In particular, we determine the cop numbers for two-dimensional Cartesian grids and tori up to an additive constant, and we give asymptotic bounds for the cop numbers of higher-dimensional grids and hypercubes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|