How many lions are needed to clear a grid?

DOI10.3390/a2031069zbMath1461.91049OpenAlexW2082754619MaRDI QIDQ1662492

Florian Berger, Alexander Gilbers, Rolf Klein, Ansgar Grüne

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a2031069

zbMATH Keywords

isoperimetric inequalitygraph searchpursuit gameslion and manavoidance numbersafe path planninggraph separator

Mathematics Subject Classification ID

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

Related Items

Searching for an intruder on graphs and their subdivisions ⋮ A local strategy for cleaning expanding cellular domains by simple robots ⋮ Lions and contamination: monotone clearings ⋮ Reversibility properties of the fire-fighting problem in graphs ⋮ Improved bounds for cops-and-robber pursuit ⋮ On a Fire Fighter’s Problem ⋮ Geometric firefighting in the half-plane ⋮ Lions and contamination, triangular grids, and Cheeger constants

Uses Software

• OEIS

Cites Work

• Compressions and isoperimetric inequalities
• Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning
• Escaping offline searchers and isoperimetric theorems
• Vertex-to-vertex pursuit in a graph
• A Separator Theorem for Planar Graphs
• “Lion and Man”: Upper and Lower Bounds
• Recontamination does not help to search a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item