A cop and drunken robber game on n-dimensional infinite-grid graphs

Journal article

Authors/Editors

Strategic Research Themes

Computational Science and Engineering (Digital Transformation)

Publication Details

Author list: Songsuwan N., Jiarasuksakun T., Tangthanawatsakul A., Kaemawichanurat P.

Publisher: MDPI

Publication year: 2021

Volume number: 9

Issue number: 17

ISSN: 22277390

eISSN: 2227-7390

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85114256878&doi=10.3390%2fmath9172107&partnerID=40&md5=1585b5fead4e9ece039167794689fde5

Languages: English-Great Britain (EN-GB)

View in Web of Science | View on publisher site | View citing articles in Web of Science

Abstract

A Cop and Drunken Robber (CDR) game is one variation of a famous combinatorial game, called Cops and Robbers, which has been extensively studied and applied in the area of theoretical and computer science as demonstrated by several conferences and publications. In this paper, for a natural number n, we present two strategies for a single cop to chase a drunken robber on n-dimensional infinite-grid graphs. Both strategies show that if the initial distance between the cop and the drunken robber is s, then the expected capture time is s + o(s). © 2021 by the authors. Licensee MDPI, Basel, Switzerland.

Keywords

Cops and Robbers, Expected capture time, Pursuit evasion, Random walks