Name
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 i 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 Theta(n(d-1)/root d) lions are necessary and sufficient to clear the n(d)-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.3390/a2031069 | ALGORITHMS |
Keywords | Field | DocType |
lion and man, safe path planning, avoidance number, pursuit games, graph separator, graph search, isoperimetric inequality | Mathematical optimization,Combinatorics,Vertex (geometry),Clearance,Lattice graph,Isoperimetric inequality,Mathematics,Grid | Journal |
Volume | Issue | ISSN |
2 | 3 | 1999-4893 |
Citations | PageRank | References |
4 | 1.16 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Florian Berger | 1 | 23 | 7.05 |
| Alexander Gilbers | 2 | 4 | 1.50 |
| Ansgar Grüne | 3 | 82 | 8.73 |
| Rolf Klein | 4 | 46 | 5.08 |