On edge-periodic graphs, deciding the winner in one-cop-one-robber play takes O(LCM(L) n^3) time, and cycles of length at least 2 l LCM(L) are always robber-win.
Cops and Robbers, Game Theory and Zermelo's Early Results
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We provide a game theoretic framework for the game of cops and robbers (CR). Within this framework we study certain assumptions which underlie the concepts of optimal strategies and capture time. We also point out a connection of these concepts to early work by Zermelo and D. Konig. Finally, we discuss the relationship between CR and related pursuit games to reachability games.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity
On edge-periodic graphs, deciding the winner in one-cop-one-robber play takes O(LCM(L) n^3) time, and cycles of length at least 2 l LCM(L) are always robber-win.