The capture time of a graph

DOI10.1016/J.DISC.2008.04.004MaRDI QIDQ1045043zbMATH OpenOpenAlexFDO

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

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

bounded-time cop numbercapture timechordal graphcop numbergraphinfinite random graphNP-completesearch number

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Games involving graphs (91A43)

Recommendations

• Bounds on the length of a game of cops and robbers
• scientific article; zbMATH DE number 5989957
• Cop-win graphs with maximum capture-time
• scientific article; zbMATH DE number 5241699
• A tight lower bound for the capture time of the cops and robbers game

Cites work

• A note on \(k\)-cop, \(l\)-robber games on graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• An annotated bibliography on guaranteed graph searching
• Asymmetric graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 5241699 (Why is no real title available?)
• On cop-win graphs
• On the cop number of a graph
• Searching and sweeping graphs: a brief survey
• The complexity of pursuit on a graph
• The cop density of a graph
• The random graph
• Vertex-to-vertex pursuit in a graph

Cited in

(45)

• 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
• A faster algorithm for cops and robbers
• 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
• Cop vs. gambler
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• Pursuit evasion on infinite graphs
• Lower bounds for the capture time: linear, quadratic, and beyond
• The cop density of a graph
• Capturing the drunk robber on a graph
• The damage throttling number of a graph
• Game with Slow Pursuers on the Edge Graphs of Regular Simplexes
• 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
• Cops and robbers ordinals of cop-win trees
• The damage number of a graph
• Conjectures on cops and robbers
• The capture time of grids
• Fast edge searching and fast searching on graphs
• A cops and robber game and the meeting time of synchronous directed walks
• Optimal number of pursuers in the game on the 1-skeleton of 4D cube
• Time-delayed cops and robbers
• Complexity results for a cops and robber game on directed graphs
• Pursuit differential games on the 1-skeleton of the truncated tetrahedron
• Capturing an invisible robber using separators
• Throttling for the game of cops and robbers on graphs
• Bounds on the length of a game of cops and robbers
• Playing snake on a graph
• Localization game capture time of trees and outerplanar graphs
• Linguistic geometry approach for solving the cops and robber problem in grid environments
• Cop-win graphs with maximum capture-time

This page was built for publication: The capture time of a graph

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