On the computational complexity of a game of cops and robbers

DOI10.1016/j.tcs.2012.11.041zbMath1290.68050arXiv1202.6043OpenAlexW1978284948MaRDI QIDQ1945941

Marcello Mamino

Publication date: 17 April 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.6043

zbMATH Keywords

computational complexitycops and robberpursuit game

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (9)

Unnamed Item ⋮ Cops and robbers on intersection graphs ⋮ The guarding game is E-complete ⋮ Cops and robber on butterflies, grids, and AT-free graphs ⋮ To satisfy impatient web surfers is hard ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Cops and robbers is EXPTIME-complete ⋮ Bounds on the length of a game of cops and robbers ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems

This page was built for publication: On the computational complexity of a game of cops and robbers