Characterizations and algorithms for generalized cops and robbers games

zbMATH Open1376.05087arXiv1704.05655MaRDI QIDQ4598355FDOQ4598355

Authors: Anthony Bonato, Gary MacGillivray 

Publication date: 20 December 2017

Abstract: We propose a definition of generalized Cops and Robbers games where there are two players, the Pursuer and the Evader, who each move via prescribed rules. If the Pursuer can ensure that the game enters into a fixed set of final positions, then the Pursuer wins; otherwise, the Evader wins. A relational characterization of the games where the Pursuer wins is provided. A precise formula is given for the length of the game, along with an algorithm for computing if the Pursuer has a winning strategy whose complexity is a function of the parameters of the game. For games where the position of one player does not affect the available moves of he other, a vertex elimination ordering characterization, analogous to a cop-win ordering, is given for when the Pursuer has a winning strategy.

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

Recommendations

• On a characterization of evasion strategies for pursuit-evasion games on graphs
• Some game-theoretic remarks on two-player generalized cops and robbers games
• The complexity of pursuit on a graph
• scientific article; zbMATH DE number 5241699
• A note on \(k\)-cop, \(l\)-robber games on graphs

zbMATH Keywords

cops and robbersdirected graphsrelational characterizationvertex elimination ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cited In (18)

• General cops and robbers games with randomness
• The optimal capture time of the one-cop-moves game
• A cop and robber game on edge-periodic temporal graphs
• Characterizations of \(k\)-copwin graphs
• Cops \& robber on periodic temporal graphs: characterization and improved bounds
• Cops and Robbers on Dynamic Graphs: Offline and Online Case
• Simultaneously moving cops and robbers
• Selfish cops and active robber: multi-player pursuit evasion on graphs
• A note on \(k\)-cop, \(l\)-robber games on graphs
• The one-cop-moves game on planar graphs
• Generalized cops and robbers: a multi-player pursuit game on graphs
• The game of overprescribed Cops and Robbers played on graphs
• Some game-theoretic remarks on two-player generalized cops and robbers games
• On a characterization of evasion strategies for pursuit-evasion games on graphs
• A survey on the relationship between the game of cops and robbers and other game representations
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• Cops and robbers ordinals of cop-win trees
• Selfish cops and passive robber: qualitative games

This page was built for publication: Characterizations and algorithms for generalized cops and robbers games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598355)