Cops and invisible robbers: the cost of drunkenness

DOI10.1016/j.tcs.2013.01.032zbMath1291.91039arXiv1201.0946OpenAlexW2963514297MaRDI QIDQ385064

Dieter Mitsche, Athanasios Kehagias, Paweł Prałat

Publication date: 29 November 2013

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

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

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81)

Related Items

Simultaneously moving cops and robbers, A probabilistic version of the game of zombies and survivors on graphs, An Introduction to Lazy Cops and Robbers on Graphs, Limited visibility cops and robber, Selfish cops and active robber: multi-player pursuit evasion on graphs, Lazy Cops and Robbers on Hypercubes, The capture time of the hypercube, Selfish cops and passive robber: qualitative games, Burning graphs: a probabilistic perspective, Zero-visibility cops and robber and the pathwidth of a graph, Containment game played on random graphs: another zig-zag theorem, Chasing a drunk robber in many classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pursuit-evasion games with incomplete information in discrete time
• The role of information in the cop-robber game
• An annotated bibliography on guaranteed graph searching
• A witness version of the cops and robber game
• Universally measurable strategies in zero-sum stochastic games
• Theory of optimal search
• Markov games with incomplete information
• Vertex-to-vertex pursuit in a graph
• Some remarks on cops and drunk robbers
• Cops and robbers in a random graph
• Pursuing a fast robber on a graph
• Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times
• A survey of algorithmic methods for partially observed Markov decision processes
• Meyniel's conjecture holds for random graphs
• Probability on Trees and Networks
• Chasing robbers on random graphs: Zigzag theorem
• Pursuit-Evasion in Models of Complex Networks
• State of the Art—A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms
• Algorithms for stochastic games ? A survey
• An Approximation Theorem for Infinite Games
• The Asymptotic Theory of Stochastic Games
• The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
• The optimal search for a Markovian target when the search path is constrained: the infinite-horizon case
• Randomized Pursuit-Evasion with Local Visibility
• Recursive matrix games
• Stochastic Games
• Stochastic games