{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:21:04Z","timestamp":1760440864877,"version":"build-2065373602"},"reference-count":14,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2009,9,7]],"date-time":"2009-09-07T00:00:00Z","timestamp":1252281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 &gt; 2 and prove that \u0398(nd-1\/\u221ad) 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.<\/jats:p>","DOI":"10.3390\/a2031069","type":"journal-article","created":{"date-parts":[[2009,9,7]],"date-time":"2009-09-07T12:08:22Z","timestamp":1252325302000},"page":"1069-1086","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["How Many Lions Are Needed to Clear a Grid?"],"prefix":"10.3390","volume":"2","author":[{"given":"Florian","family":"Berger","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Bonn, 53117 Bonn, Germany"}]},{"given":"Alexander","family":"Gilbers","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn, 53117 Bonn, Germany"}]},{"given":"Ansgar","family":"Gr\u00fcne","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn, 53117 Bonn, Germany"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn, 53117 Bonn, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2009,9,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1287\/ijoc.4.4.447","article-title":"\u2018Lion and man\u2019: Upper and lower bounds","volume":"4","author":"Alonso","year":"1992","journal-title":"ORSA J. Comput."},{"key":"ref_2","unstructured":"Berger, F., Gr\u00fcne, A., and Klein, R. (2007). How many lions can one man avoid?, Department of Computer Science I. Technical Report 006."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","article-title":"Graph searching, path-width, tree-width and related problems","volume":"5","author":"Bienstock","year":"1991","journal-title":"DIMACS Ser. Dis. Math. Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0097-3165(91)90021-8","article-title":"Compressions and isoperimetric inequalities","volume":"56","author":"Leader","year":"1991","journal-title":"J. Combinat. Theory Ser. A"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.comgeo.2008.08.001","article-title":"Escaping offline searchers and isoperimetric theorems","volume":"42","author":"Brass","year":"2009","journal-title":"Comput. Geom."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.tcs.2008.02.039","article-title":"Offline variants of the \u201clion and man\u201d problem","volume":"399","author":"Dumitrescu","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","unstructured":"Galtier, J. (1996). Lower bounds for \u03b3-cuts on multi-dimensional rectangular grids, PRiSM. Technical Report 1995\/36."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/151261.151263","article-title":"Recontamination does not help to search a graph","volume":"40","author":"LaPaugh","year":"1993","journal-title":"JACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1977","journal-title":"SIAM J. Appl. Math."},{"key":"ref_10","unstructured":"Littlewood, J.E. (1953). A mathematician\u2019s Miscellany, Methuen."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","article-title":"Vertex-to-vertex pursuit in a graph","volume":"43","author":"Nowakowski","year":"1983","journal-title":"Dis. Math."},{"key":"ref_12","unstructured":"Penninger, R. (2008). Diploma thesis, University of Bonn."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BFb0070400","article-title":"Pursuit-evasion in a graph","volume":"642","author":"Parsons","year":"1978","journal-title":"Theory Appl. graphs"},{"key":"ref_14","unstructured":"Sloane, N.J.A. (2009). The On-Line Encyclopedia of Integer Sequences, Available online: http:\/\/www.research.att.com\/\u223cnjas\/sequences\/; AT&T Research."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/1069\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:11:07Z","timestamp":1760220667000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/1069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,7]]},"references-count":14,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2009,9]]}},"alternative-id":["a2031069"],"URL":"https:\/\/doi.org\/10.3390\/a2031069","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,9,7]]}}}