The capture time of a graph
From MaRDI portal
Publication:1045043
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
graph; chordal graph; NP-complete; cop number; infinite random graph; search number; capture time; bounded-time cop number
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