Cops and Robber with Constraints | Zendy

Fedor V. Fomin | Zendy; Petr A. Golovach | Zendy; Paweł Prałat | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Cops and Robber with Constraints

Author(s) -

Fedor V. Fomin,

Petr A. Golovach,

Paweł Prałat

Publication year - 2012

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/110837759

Subject(s) - mathematics , combinatorics , pursuit evasion , task (project management) , mathematical optimization , discrete mathematics , computer science , mathematical economics , theoretical computer science , economics , management

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research