Bounds on the length of a game of cops and robbers

DOI10.1016/j.disc.2018.05.025zbMath1392.05082arXiv1706.08379OpenAlexW2963546058WikidataQ129682610 ScholiaQ129682610MaRDI QIDQ724868

William B. Kinnersley

Publication date: 26 July 2018

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

Full work available at URL: https://arxiv.org/abs/1706.08379

zbMATH Keywords

cops and robberscapture timemoving target searchvertex-pursit games

Mathematics Subject Classification ID

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

Related Items (8)

Capture times in the bridge-burning cops and robbers game ⋮ Unnamed Item ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Cops and robber on some families of oriented graphs ⋮ Capture-time extremal cop-win graphs ⋮ The localization capture time of a graph

Cites Work

• Unnamed Item
• The capture time of grids
• The complexity of pursuit on a graph
• A game of cops and robbers
• Cop-win graphs with maximum capture-time
• The capture time of a graph
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• On the computational complexity of a game of cops and robbers
• The capture time of the hypercube
• Cops and robbers is EXPTIME-complete
• The game of overprescribed Cops and Robbers played on graphs
• Variations on cops and robbers
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond
• Cops and Robbers on Planar‐Directed Graphs
• A Tight Lower Bound for the Capture Time of the Cops and Robbers Game

This page was built for publication: Bounds on the length of a game of cops and robbers