Characterizations and algorithms for generalized cops and robbers games

<a class="pub-badge pub-badge--grey" href="https://zbmath.org/1376.05087" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q4598355" rel="nofollow">MaRDI QID Q4598355</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q4598355" rel="nofollow">FDO</a>

Authors Anthony Bonato, Gary MacGillivray

Publication date 20 December 2017

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

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)

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.

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

Cited in

(18)

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

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)