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.039MaRDI QIDQ930894zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Maximum thick paths in static and dynamic environments
• Motion planning in the presence of moving obstacles
• Planning the Shortest Safe Path Amidst Unpredictably Moving Obstacles
• Best laid plans of lions and men
• Solution of David Gale's lion and man problem

Cites work

• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 1164584 (Why is no real title available?)
• scientific article; zbMATH DE number 3799443 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• scientific article; zbMATH DE number 3080510 (Why is no real title available?)
• An annotated bibliography on guaranteed graph searching
• Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem
• Fugitive-search games on graphs and related parameters
• Motion planning in the presence of moving obstacles
• Probability and Computing
• Solution of David Gale's lion and man problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertex-to-vertex pursuit in a graph
• Vision-Based Pursuit-Evasion in a Grid
• “Lion and Man”: A Postscript
• “Lion and Man”: Upper and Lower Bounds

Cited in

(8)

• scientific article; zbMATH DE number 5507802 (Why is no real title available?)
• Reversibility properties of the fire-fighting problem in graphs
• Lions and contamination, triangular grids, and Cheeger constants
• Bounds for cops and robber pursuit
• How many lions are needed to clear a grid?
• Approximate capture in Gromov-Hausdorff close spaces
• Geometric firefighting in the half-plane
• Improved bounds for cops-and-robber pursuit

This page was built for publication: Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning

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