General cops and robbers games with randomness

DOI10.1016/j.tcs.2021.06.043OpenAlexW3180606547MaRDI QIDQ820532

François Laviolette, Frédéric Simard, Josée Desharnais

Publication date: 27 September 2021

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

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

zbMATH Keywords

graph theorystochastic gamesoptimal strategiespursuit gamescops and robbers games

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Pursuit problem with a stochastic prey that sees its chasers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic version of the game of zombies and survivors on graphs
• Capturing the drunk robber on a graph
• Characterizations of \(k\)-copwin graphs
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• The complexity of stochastic games
• Vertex-to-vertex pursuit in a graph
• Some remarks on cops and drunk robbers
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• Selfish cops and active robber: multi-player pursuit evasion on graphs
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Cop and Robber Games When the Robber Can Hide and Ride
• On Markov games
• Characterizations and algorithms for generalized Cops and Robbers games
• Technical Note—The Complexity of the Optimal Searcher Path Problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Stochastic Games