{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T04:43:18Z","timestamp":1667364198918},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Petchra Pra Jom Klao Ph.D. Research Scholarship from King Mongkut\u2019s University of Technology Thonburi","award":["33\/2563"],"award-info":[{"award-number":["33\/2563"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Dyn Games Appl"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>expected drunk capture times<\/jats:italic><jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textit{dct}}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>dct<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph <jats:italic>G<\/jats:italic>. We apply the concepts of expected hitting time in Markov Chain and combinatorial technique to find <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textit{dct}}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>dct<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for graphs <jats:italic>G<\/jats:italic> that have been used in many applications which are cycles, complete multipartite graphs, grid graphs and prism graphs.<\/jats:p>","DOI":"10.1007\/s13235-022-00444-0","type":"journal-article","created":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T15:02:48Z","timestamp":1650639768000},"page":"1312-1337","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Chasing a Drunk Robber in Many Classes of Graphs"],"prefix":"10.1007","volume":"12","author":[{"given":"Nuttanon","family":"Songsuwan","sequence":"first","affiliation":[]},{"given":"Dawud","family":"Thongtha","sequence":"additional","affiliation":[]},{"given":"Pawaton","family":"Kaemawichanurat","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"key":"444_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(84)90073-8","volume":"8","author":"M Aigner","year":"1984","unstructured":"Aigner M, Fromme M (1984) A game of cops and robbers. Discret Appl Math 8:1\u201312","journal-title":"Discret Appl Math"},{"key":"444_CR2","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1017\/S0963548312000338","volume":"21","author":"A Beveridge","year":"2012","unstructured":"Beveridge A, Dudek Frieze A, Muller T (2012) Cops and robbers in geometric graphs. Comb Probab Comput 21:816\u2013834","journal-title":"Comb Probab Comput"},{"key":"444_CR3","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10514-011-9241-4","volume":"31","author":"TH Chung","year":"2011","unstructured":"Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robot 31:299\u2013316","journal-title":"Auton Robot"},{"key":"444_CR4","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00373-012-1246-z","volume":"30","author":"NE Clarke","year":"2014","unstructured":"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\u2013124","journal-title":"Graphs Comb"},{"key":"444_CR5","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.dam.2017.03.004","volume":"225","author":"SL Fitzpatrick","year":"2017","unstructured":"Fitzpatrick SL, Larkin JP (2017) The game of cops and robber on circulant graphs. Discret Appl Math 225:64\u201373","journal-title":"Discret Appl Math"},{"key":"444_CR6","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/s00224-011-9360-5","volume":"50","author":"FV Fomin","year":"2012","unstructured":"Fomin FV, Golovach PA, Lokshtanov D (2012) Cops and robber game without recharging. Theory Comput Syst 50:611\u2013620","journal-title":"Theory Comput Syst"},{"key":"444_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.ejc.2018.04.009","volume":"72","author":"T Gavenciak","year":"2018","unstructured":"Gavenciak T, Gordinowicz P, Jelinek V, Klavik P, Kratochvil J (2018) Cops and robbers on intersection graphs. Eur J Comb 72:45\u201369","journal-title":"Eur J Comb"},{"issue":"5","key":"444_CR8","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1109\/TRO.2005.851373","volume":"21","author":"V Isler","year":"2005","unstructured":"Isler V, Kannan S, Khanna S (2005) Randomized pursuit\u2013evasion in a polygonal environment. IEEE Trans Robotics 21(5):875\u2013884","journal-title":"IEEE Trans Robotics"},{"key":"444_CR9","unstructured":"Kehagias A, Pra\u0142at P (2011) Cops and visible robbers: a computational approach. (Manuscript)"},{"key":"444_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2012.08.016","volume":"463","author":"A Kehagias","year":"2012","unstructured":"Kehagias A, Pra\u0142at P (2012) Some remarks on cops and drunk robbers. Theoret Comput Sci 463:133\u2013147","journal-title":"Theoret Comput Sci"},{"key":"444_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2013.01.032","volume":"481","author":"A Kehagias","year":"2013","unstructured":"Kehagias A, Mitsche D, Pra\u0142at P (2013) Cops and invisible robbers: the cost of drunkenness. Theoret Comput Sci 481:100\u2013120","journal-title":"Theoret Comput Sci"},{"key":"444_CR12","unstructured":"Komarov N (2013) Capture time in variants of cops & robbers games. Thesis for the degree of Doctor of Philosophy in Mathematics, Dartmouth College"},{"issue":"3","key":"444_CR13","first-page":"1","volume":"21","author":"N Komarov","year":"2014","unstructured":"Komarov N, Winkler P (2014) Catching the drunk robber on a graph. Electron J Comb 21(3):1\u201314","journal-title":"Electron J Comb"},{"key":"444_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.tcs.2016.06.039","volume":"645","author":"G Konstantinidis","year":"2016","unstructured":"Konstantinidis G, Kehagias A (2016) Simultaneously moving cops and robbers. Theoret Comput Sci 645:48\u201359","journal-title":"Theoret Comput Sci"},{"key":"444_CR15","unstructured":"Lehner F (2019) On the cop number of toroidal graphs. (Submitted)"},{"key":"444_CR16","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.disc.2010.10.002","volume":"311","author":"A Mehrabian","year":"2011","unstructured":"Mehrabian A (2011) The capture time of grid. Discret Math 311:102\u2013105","journal-title":"Discret Math"},{"key":"444_CR17","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","volume":"43","author":"RJ Nowakowski","year":"1983","unstructured":"Nowakowski RJ, Winkler P (1983) Vertex to vertex pursuit in a graph. Discret Math 43:235\u2013239","journal-title":"Discret Math"},{"key":"444_CR18","doi-asserted-by":"crossref","unstructured":"Offner D, Ojakian K (2019) Capture-time extremal cop-win graphs. Discuss Math Graph Theory","DOI":"10.7151\/dmgt.2224"},{"key":"444_CR19","doi-asserted-by":"crossref","unstructured":"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\u201317","DOI":"10.1007\/978-3-319-48749-6_1"},{"key":"444_CR20","unstructured":"Quilliot A (1985) Jeux et pointes fixes sur les graphes, th\u00e8se de 3\u00e8me cycle [Games and fixed points on graphs, Ph.D. Thesis]. Universite de Paris VI, pp 131\u2013145 (in French)"},{"issue":"3","key":"444_CR21","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1214\/aoms\/1177731235","volume":"15","author":"A Wald","year":"1944","unstructured":"Wald A (1944) On cumulative sums of random variables. Ann Math Stat 15(3):283\u2013296","journal-title":"Ann Math Stat"},{"key":"444_CR22","first-page":"225","volume":"109","author":"NTh Varopoulos","year":"1985","unstructured":"Varopoulos NTh (1985) Long range estimations for Markov chains. Bull Sci Math 109:225\u2013252","journal-title":"Bull Sci Math"}],"container-title":["Dynamic Games and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-022-00444-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13235-022-00444-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-022-00444-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,1]],"date-time":"2022-11-01T20:44:01Z","timestamp":1667335441000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13235-022-00444-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["444"],"URL":"https:\/\/doi.org\/10.1007\/s13235-022-00444-0","relation":{},"ISSN":["2153-0785","2153-0793"],"issn-type":[{"value":"2153-0785","type":"print"},{"value":"2153-0793","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"assertion":[{"value":"21 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}