Even flying cops should think ahead
From MaRDI portal
Publication:1661906
DOI10.1007/978-3-319-96151-4_28zbMATH Open1404.90118arXiv1801.07193OpenAlexW2963825610MaRDI QIDQ1661906FDOQ1661906
Angelika Steger, Patrick Schnider, Florian Meier, Anders Martinsson
Publication date: 17 August 2018
Abstract: We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to catch a robber in G, we show that the required number of cops can be much larger, even for graphs with small maximum degree. In particular, we show that there are 3-regular graphs where a linear number of cops are needed.
Full work available at URL: https://arxiv.org/abs/1801.07193
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Positional games (pursuit and evasion, etc.) (91A24)
Cited In (1)
This page was built for publication: Even flying cops should think ahead
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661906)
