How Many Lions Are Needed to Clear a Grid?
Open Access
- 7 September 2009
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 2 (3) , 1069-1086
Abstract
We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. Brass et al. [5] showed that n/2 lions are not enough to clear the n x n-grid. In this paper, we consider the same problem in dimension d > 2 and prove that Θ(nd-1/√d) lions are necessary and sufficient to clear the nd-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.Keywords
This publication has 9 references indexed in Scilit:
- Escaping offline searchers and isoperimetric theoremsComputational Geometry, 2009
- Offline variants of the “lion and man” problemTheoretical Computer Science, 2008
- Recontamination does not help to search a graphJournal of the ACM, 1993
- “Lion and Man”: Upper and Lower BoundsINFORMS Journal on Computing, 1992
- Graph searching, path-width, tree-width and related problems (A survey)1991
- Compressions and isoperimetric inequalitiesJournal of Combinatorial Theory, Series A, 1991
- Vertex-to-vertex pursuit in a graphDiscrete Mathematics, 1983
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Pursuit-evasion in a graph1978