The capture time of a graph

DOI10.1016/j.disc.2008.04.004zbMath1177.91056MaRDI QIDQ1045043

Jan Kratochvíl, Anthony Bonato, Geňa Hahn, Petr A. Golovach

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.004

zbMATH Keywords

graph; chordal graph; NP-complete; cop number; infinite random graph; search number; capture time; bounded-time cop number

Mathematics Subject Classification ID

91A43: Games involving graphs

05C75: Structural characterization of families of graphs

Related Items

Game with Slow Pursuers on the Edge Graphs of Regular Simplexes, Unnamed Item, Differential Game with Slow Pursuers on the Edge Graph of a Simplex, TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS, The damage throttling number of a graph, Conjectures on Cops and Robbers, Cop vs. gambler, Pursuit evasion on infinite graphs, Capturing the drunk robber on a graph, Cops and robbers ordinals of cop-win trees, The capture time of grids, Fast edge searching and fast searching on graphs, Throttling for the game of cops and robbers on graphs, Bounds on the length of a game of cops and robbers, Linguistic geometry approach for solving the cops and robber problem in grid environments, Cop-win graphs with maximum capture-time, The capture time of a planar graph, Visibility graphs, dismantlability, and the cops and robbers game, The impact of loops on the game of cops and robbers on graphs, The capture time of the hypercube, The game of cops and eternal robbers, Capture-time extremal cop-win graphs, A pursuit-evasion differential game with slow pursuers on the edge graph of a simplex. I, Product throttling, The localization capture time of a graph, Capture times in the bridge-burning cops and robbers game, Constructible graphs and pursuit, Containment: a variation of cops and robber, A tight lower bound for the capture time of the cops and robbers game, Zombie number of the Cartesian product of graphs, The optimal capture time of the one-cop-moves game, The game of overprescribed Cops and Robbers played on graphs, On the Capture Time of Cops and Robbers Game on a Planar Graph, Unnamed Item, Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of pursuit on a graph
• An annotated bibliography on guaranteed graph searching
• On the cop number of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Vertex-to-vertex pursuit in a graph
• On cop-win graphs
• A note on \(k\)-cop, \(l\)-robber games on graphs
• The random graph
• Asymmetric graphs