IDEAS home Printed from https://ideas.repec.org/a/spr/dyngam/v12y2022i4d10.1007_s13235-022-00444-0.html
   My bibliography  Save this article

Chasing a Drunk Robber in Many Classes of Graphs

Author

Listed:
  • 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)

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.

Suggested Citation

  • Nuttanon Songsuwan & Dawud Thongtha & Pawaton Kaemawichanurat, 2022. "Chasing a Drunk Robber in Many Classes of Graphs," Dynamic Games and Applications, Springer, vol. 12(4), pages 1312-1337, December.
    • Handle: RePEc:spr:dyngam:v:12:y:2022:i:4:d:10.1007_s13235-022-00444-0
    DOI: 10.1007/s13235-022-00444-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13235-022-00444-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13235-022-00444-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:dyngam:v:12:y:2022:i:4:d:10.1007_s13235-022-00444-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.