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

DOI10.4230/LIPICS.ICALP.2017.82zbMATH Open1447.91028OpenAlexW2741158200MaRDI QIDQ5111413FDOQ5111413

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

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7413/pdf/LIPIcs-ICALP-2017-82.pdf

Recommendations

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

zbMATH Keywords

lower boundcops and robberscapture time

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24)

Cited In (10)

• A tight lower bound for semi-synchronous collaborative grid exploration
• A tight lower bound for the capture time of the cops and robbers game
• The capture time of a graph
• Fine-grained Lower Bounds on Cops and Robbers
• Capture times in the bridge-burning cops and robbers game
• Bounds on the length of a game of cops and robbers
• Cop-win graphs with maximum capture-time
• 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
• A simple method for proving lower bounds in the zero-visibility cops and robber game

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 Q5111413)