How many lions are needed to clear a grid?

DOI10.3390/A2031069MaRDI QIDQ1662492zbMATH OpenOpenAlexFDO

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

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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 on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Recommendations

• Lions and contamination: monotone clearings
• Lions and contamination, triangular grids, and Cheeger constants
• Best laid plans of lions and men
• Escaping an infinitude of lions
• \(k\)-capture in multiagent pursuit evasion, or the lion and the hyenas

Cites work

• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 3080510 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Compressions and isoperimetric inequalities
• Escaping offline searchers and isoperimetric theorems
• Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning
• Recontamination does not help to search a graph
• The On-Line Encyclopedia of Integer Sequences
• Vertex-to-vertex pursuit in a graph
• “Lion and Man”: Upper and Lower Bounds

Cited in

(9)

• On a fire fighter's problem
• Searching for an intruder on graphs and their subdivisions
• A local strategy for cleaning expanding cellular domains by simple robots
• Reversibility properties of the fire-fighting problem in graphs
• Lions and contamination, triangular grids, and Cheeger constants
• Lions and contamination: monotone clearings
• Geometric firefighting in the half-plane
• Improved bounds for cops-and-robber pursuit
• Non-adaptive and adaptive two-sided search with fast objects

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: How many lions are needed to clear a grid?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662492)