The game of cops and eternal robbers

DOI10.1016/J.TCS.2021.05.014MaRDI QIDQ2034413zbMATH OpenOpenAlexFDO

Authors Melissa Huggan, Trent Gregory Marbach, Anthony Bonato, Fionn Mc Inerney

Publication date 22 June 2021

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

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

zbMATH Keywords

treesgraph algorithmscops and robbersgridspursuit-evasion gamesretracts

Mathematics Subject Classification ID

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

Recommendations

• A game of cops and robbers
• scientific article; zbMATH DE number 4064802
• On a game of policemen and robber
• A witness version of the cops and robber game
• scientific article; zbMATH DE number 7232976
• Variations on cops and robbers
• Cop and robber game and hyperbolicity
• scientific article; zbMATH DE number 2170338
• Cops and robbers is EXPTIME-complete
• Cops and Robber game without recharging

Cites work

• scientific article; zbMATH DE number 5575574 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2174620 (Why is no real title available?)
• A note on the eternal dominating set problem
• Closing the gap: eternal domination on \(3 \times n\) grids
• Conjoined games: \textsc{go-cut} and \textsc{sno-go}
• Cops and robbers is EXPTIME-complete
• Eternal domination in split graphs
• Eternal domination numbers of \(4\times n\) grid graphs
• Eternal domination: \(D\)-dimensional Cartesian and strong grids and everything in between
• Meyniel's conjecture on the cop number: a survey
• Packing and covering a tree by subtrees
• Spy-game on graphs: complexity and simple topologies
• Study of a combinatorial game in graphs through linear programming
• The capture time of a graph
• The capture time of grids
• The game of cops and robbers on graphs
• Time constrained graph searching
• Topological directions in cops and robbers

Cited in

(12)

• Cop-robber guarding game with cycle robber-region
• Cops, a fast robber and defensive domination on interval graphs
• A game theoretic analysis of the cops and robber game
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• scientific article; zbMATH DE number 4064802 (Why is no real title available?)
• Spy-game on graphs
• The Game of Cops and Eternal Robbers
• Continuous Patrolling Games
• The robber locating game
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• scientific article; zbMATH DE number 2170338 (Why is no real title available?)
• A game of cops and robbers on graphs with periodic edge-connectivity

This page was built for publication: The game of cops and eternal robbers

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