A tight lower bound for the capture time of the cops and robbers game

DOI10.1016/J.TCS.2020.06.004MaRDI QIDQ2196569zbMATH OpenOpenAlexFDO

Authors Yuval Emek, Jara Uitto, Roger Wattenhofer, Sebastian F. Brandt

Publication date 3 September 2020

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

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7413/

zbMATH Keywords

cops and robberslower boundmobile agents

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Review text

The authors answer on the negative to a question by \textit{A. Bonato} and \textit{R. J. Nowakowski} [The game of cops and robbers on graphs. Providence, RI: American Mathematical Society (AMS) (2011; Zbl 1298.91004)] on the impossibility of improving the known lower bound of the capture time in the \(k\)-cop-win graphs, \(k\geq 2\), pertaining to the game of cops and robbers. This is in sharp contrast with the \(k=1\) case.

Recommendations

• A tight lower bound for the capture time of the cops and robbers game
• Bounds on the length of a game of cops and robbers
• Lower bounds for the capture time: linear, quadratic, and beyond
• The capture time of a graph
• Cop-win graphs with maximum capture-time

Cites work

• A game of cops and robbers
• A tight lower bound for the capture time of the cops and robbers game
• An annotated bibliography on guaranteed graph searching
• Bounds on the length of a game of cops and robbers
• Characterizations of k-copwin graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• scientific article; zbMATH DE number 5241699 (Why is no real title available?)
• Lower bounds for the capture time: linear, quadratic, and beyond
• Meyniel's conjecture on the cop number: a survey
• On a pursuit game played on graphs for which a minor is excluded
• On Meyniel's conjecture of the cop number
• On the cop number of a graph
• Searching and sweeping graphs: a brief survey
• Some remarks on cops and drunk robbers
• The capture time of a graph
• The capture time of grids
• The capture time of the hypercube
• The game of cops and robbers on graphs
• Vertex-to-vertex pursuit in a graph
• When does a random graph have constant cop number?

Cited in

(12)

• The localization capture time of a graph
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• A partition approach to lower bounds for zero-visibility cops and robber
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• scientific article; zbMATH DE number 5989957 (Why is no real title available?)
• Lower bounds for the capture time: linear, quadratic, and beyond
• A tight lower bound for the capture time of the cops and robbers game
• Cops and robber on butterflies, grids, and AT-free graphs
• A cops and robber game and the meeting time of synchronous directed walks
• Complexity results for a cops and robber game on directed graphs
• Bounds on the length of a game of cops and robbers
• Localization game capture time of trees and outerplanar graphs

This page was built for publication: A tight lower bound for the capture time of the cops and robbers game

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