Chasing a Drunk Robber in Many Classes of Graphs
Journal article
Authors/Editors
Strategic Research Themes
Publication Details
Author list: Songsuwan, Nuttanon; Thongtha, Dawud; Kaemawichanurat, Pawaton;
Publisher: Springer
Publication year: 2022
Volume number: 12
Issue number: 4
Start page: 1
End page: 26
Number of pages: 26
ISSN: 2153-0785
eISSN: 2153-0793
Languages: English-Great Britain (EN-GB)
View in Web of Science | View on publisher site | View citing articles in Web of Science
Abstract
A cops and robbers game (CR) on graphs was originated in 1983 by Quilliot and by Nowakowski and Winkler independently. This game has been applied in many problems in the area of theoretical computer science such as information seeking, robot motion planning or network security as evidenced by many conferences and publications. The CR game has also been extensively studied and varied to many versions. In this paper, we focus on CR game under the condition that the robber performs a random walk. Namely, he drunkenly, or randomly, chooses his next move to escape the cop, while the cop plays optimally in order to minimize the expected drunk capture timesdct(G) of a graph G. We apply the concepts of expected hitting time in Markov Chain and combinatorial technique to find dct(G) for graphs G that have been used in many applications which are cycles, complete multipartite graphs, grid graphs and prism graphs. © 2022, The Author(s).
Keywords
05C57, 05C8, 91A43, Pursuit–evasion
Contact Information