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

DOI10.4230/LIPICS.ICALP.2017.82MaRDI QIDQ5111413zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2020

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

zbMATH Keywords

capture timecops and robberslower bound

Mathematics Subject Classification ID

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

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

Cited in

(12)

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

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)