Chasing a Drunk Robber in Many Classes of Graphs

Dynamic Games and Applications - 2022
Nuttanon Songsuwan1, Dawud Thongtha1, Pawaton Kaemawichanurat1
1Mathematics and Statistics with Applications (MaSA), Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok, Thailand

Tóm tắt

AbstractA 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.

Từ khóa


Tài liệu tham khảo

Aigner M, Fromme M (1984) A game of cops and robbers. Discret Appl Math 8:1–12

Beveridge A, Dudek Frieze A, Muller T (2012) Cops and robbers in geometric graphs. Comb Probab Comput 21:816–834

Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robot 31:299–316

Clarke NE, Fiorini S, Joret G, Theis DO (2014) A note on the cops and robber game on graphs embedded in non-orientable surfaces. Graphs Comb 30:119–124

Fitzpatrick SL, Larkin JP (2017) The game of cops and robber on circulant graphs. Discret Appl Math 225:64–73

Fomin FV, Golovach PA, Lokshtanov D (2012) Cops and robber game without recharging. Theory Comput Syst 50:611–620

Gavenciak T, Gordinowicz P, Jelinek V, Klavik P, Kratochvil J (2018) Cops and robbers on intersection graphs. Eur J Comb 72:45–69

Isler V, Kannan S, Khanna S (2005) Randomized pursuit–evasion in a polygonal environment. IEEE Trans Robotics 21(5):875–884

Kehagias A, Prałat P (2011) Cops and visible robbers: a computational approach. (Manuscript)

Kehagias A, Prałat P (2012) Some remarks on cops and drunk robbers. Theoret Comput Sci 463:133–147

Kehagias A, Mitsche D, Prałat P (2013) Cops and invisible robbers: the cost of drunkenness. Theoret Comput Sci 481:100–120

Komarov N (2013) Capture time in variants of cops & robbers games. Thesis for the degree of Doctor of Philosophy in Mathematics, Dartmouth College

Komarov N, Winkler P (2014) Catching the drunk robber on a graph. Electron J Comb 21(3):1–14

Konstantinidis G, Kehagias A (2016) Simultaneously moving cops and robbers. Theoret Comput Sci 645:48–59

Lehner F (2019) On the cop number of toroidal graphs. (Submitted)

Mehrabian A (2011) The capture time of grid. Discret Math 311:102–105

Nowakowski RJ, Winkler P (1983) Vertex to vertex pursuit in a graph. Discret Math 43:235–239

Offner D, Ojakian K (2019) Capture-time extremal cop-win graphs. Discuss Math Graph Theory

Pisantechakool P, Tan X (2016) On the capture time of cops and robbers game on a planar graph. In: International conference on combinatorial optimization and applications, pp 3–17

Quilliot A (1985) Jeux et pointes fixes sur les graphes, thèse de 3ème cycle [Games and fixed points on graphs, Ph.D. Thesis]. Universite de Paris VI, pp 131–145 (in French)

Wald A (1944) On cumulative sums of random variables. Ann Math Stat 15(3):283–296

Varopoulos NTh (1985) Long range estimations for Markov chains. Bull Sci Math 109:225–252

Thông tin
Thông tin xuất bản

Dynamic Games and Applications

Thông tin tác giả