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

DOI10.1016/J.TCS.2015.04.005MaRDI QIDQ2348264zbMATH OpenOpenAlexFDO

Authors 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 gamegraph searchingcapture time

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)

Recommendations

• One-visibility cops and robber on trees: optimal cop-win strategies
• One-visibility cops and robber on trees
• The one-cop-moves game on graphs of small treewidth
• The capture time of a graph
• The one-cop-moves game on graphs with some special structures

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 5241699 (Why is no real title available?)
• scientific article; zbMATH DE number 3078991 (Why is no real title available?)
• A better bound for the cop number of general graphs
• A bound for the cops and robbers problem
• A game of cops and robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Characterizations and algorithms for generalized cops and robbers games
• Characterizations of k-copwin graphs
• Cop-win graphs with maximum capture-time
• Extensive Games
• Graphs and composite games
• On Meyniel's conjecture of the cop number
• Searching and sweeping graphs: a brief survey
• The capture time of a graph
• The capture time of grids
• The game of cops and robbers on graphs
• Variations on cops and robbers
• Vertex-to-vertex pursuit in a graph
• When does a random graph have constant cop number?
• Zero-visibility cops and robber and the pathwidth of a graph

Cited in

(9)

• The one-cop-moves game on graphs with some special structures
• Guarding isometric subgraphs and cops and robber in planar graphs
• scientific article; zbMATH DE number 7720718 (Why is no real title available?)
• Capture times in the bridge-burning cops and robbers game
• The one-cop-moves game on planar graphs
• Linguistic geometry approach for solving the cops and robber problem in grid environments
• One-visibility cops and robber on trees: optimal cop-win strategies
• 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

This page was built for publication: The optimal capture time of the one-cop-moves game

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