Randomized Pursuit-Evasion in Graphs
- 20 May 2003
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 12 (3) , 225-244
- https://doi.org/10.1017/s0963548303005625
Abstract
We analyse a randomized pursuit-evasion game played by two players on a graph, a hunter and a rabbit. Let is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits.Keywords
This publication has 0 references indexed in Scilit: