Back to Search
Start Over
Some remarks on cops and drunk robbers
- Source :
-
Theoretical Computer Science . Dec2012, Vol. 463, p133-147. 15p. - Publication Year :
- 2012
-
Abstract
- Abstract: The cops and robber game has been extensively studied under the assumption of optimal play by both the cops and the robber. In this paper we study the problem in which cops are chasing a drunk robber (that is, a robber who performs a random walk) on a graph. Our main goal is to characterize the “cost of drunkenness”. Specifically, we study the ratio of expected capture times for the optimal version and the drunk robber one. We also examine the algorithmic side of the problem; that is, how to compute near-optimal search schedules for the cops. Finally, we present a preliminary investigation of the invisible robber game and point out differences between this game and graph search. [Copyright &y& Elsevier]
- Subjects :
- *GAME theory
*RANDOM walks
*GRAPH theory
*ALGORITHMS
*SCHEDULING
*APPLIED mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 463
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 83324364
- Full Text :
- https://doi.org/10.1016/j.tcs.2012.08.016