Cops and Robber with Constraints
Fedor V. Fomin, Petr A. Golovach, Paweł Prałat · SIAM Journal on Discrete Mathematics · 2012
Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game.