The optimal capture time of the one-cop-moves game

DOI10.1016/j.tcs.2015.04.005zbMath1326.05093MaRDI QIDQ2348264

Boting Yang, William Hamilton

Publication date: 11 June 2015

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.04.005

zbMATH Keywords

cops-and-robber game; graph searching; capture time

Mathematics Subject Classification ID

91A43: Games involving graphs

05C85: Graph algorithms (graph-theoretic aspects)

91A24: Positional games (pursuit and evasion, etc.)

05C57: Games on graphs (graph-theoretic aspects)

Related Items

Unnamed Item, Linguistic geometry approach for solving the cops and robber problem in grid environments, The one-cop-moves game on planar graphs, Capture times in the bridge-burning cops and robbers game, A simple method for proving lower bounds in the zero-visibility cops and robber game, Cops and robbers on graphs with a set of forbidden induced subgraphs, The one-cop-moves game on graphs with some special structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of \(k\)-copwin graphs
• The capture time of grids
• A game of cops and robbers
• Cop-win graphs with maximum capture-time
• The capture time of a graph
• Vertex-to-vertex pursuit in a graph
• Zero-visibility cops and robber and the pathwidth of a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• A Bound for the Cops and Robbers Problem
• Characterizations and algorithms for generalized Cops and Robbers games
• A better bound for the cop number of general graphs
• Graphs and composite games
• Extensive Games