Chasing a Drunk Robber in Many Classes of Graphs

Nuttanon Songsuwan (), Dawud Thongtha () and Pawaton Kaemawichanurat ()
Additional contact information
Nuttanon Songsuwan: King Mongkut’s University of Technology Thonburi
Dawud Thongtha: King Mongkut’s University of Technology Thonburi
Pawaton Kaemawichanurat: King Mongkut’s University of Technology Thonburi

Dynamic Games and Applications, 2022, vol. 12, issue 4, No 13, 1312-1337

Abstract: 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 times $${\textit{dct}}(G)$$ dct ( G ) of a graph G. We apply the concepts of expected hitting time in Markov Chain and combinatorial technique to find $${\textit{dct}}(G)$$ dct ( G ) for graphs G that have been used in many applications which are cycles, complete multipartite graphs, grid graphs and prism graphs.

Keywords: Pursuit–evasion; Cops and robbers; Random walks; 05C57; 05C8; 91A43 (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-022-00444-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:12:y:2022:i:4:d:10.1007_s13235-022-00444-0

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-022-00444-0

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().