Abstract
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with limited visibility with high probability. We distinguish between reactive rabbits who move only when the hunter is visible and general rabbits who can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Pages | 1053-1062 |
| Number of pages | 10 |
| Volume | 15 |
| State | Published - Apr 15 2004 |
| Event | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004 |
Other
| Other | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | New Orleans, LA. |
| Period | 1/11/04 → 1/13/04 |