Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning

DOI10.1016/j.tcs.2008.02.039zbMath1146.68066OpenAlexW2028560778MaRDI QIDQ930894

Adrian Dumitrescu, Paweł Żyliński, Ichiro Suzuki

Publication date: 24 June 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.039

zbMATH Keywords

avoidance numberlion and man problemmeasuring crowdednesssafe path planning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

How many lions are needed to clear a grid? ⋮ Reversibility properties of the fire-fighting problem in graphs ⋮ Improved bounds for cops-and-robber pursuit ⋮ Bounds for cops and robber pursuit ⋮ Geometric firefighting in the half-plane ⋮ Lions and contamination, triangular grids, and Cheeger constants ⋮ Approximate capture in Gromov-Hausdorff close spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• Fugitive-search games on graphs and related parameters
• Vertex-to-vertex pursuit in a graph
• “Lion and Man”: Upper and Lower Bounds
• Motion planning in the presence of moving obstacles
• “Lion and Man”: A Postscript
• Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem
• Probability and Computing
• Vision-Based Pursuit-Evasion in a Grid
• Solution of David Gale's lion and man problem