Cops and Robbers with Speed Restrictions
Author | : Sebastián González Hermosillo de la Maza |
Publisher | : |
Total Pages | : 53 |
Release | : 2019 |
ISBN-10 | : OCLC:1144864560 |
ISBN-13 | : |
Rating | : 4/5 ( Downloads) |
Download or read book Cops and Robbers with Speed Restrictions written by Sebastián González Hermosillo de la Maza and published by . This book was released on 2019 with total page 53 pages. Available in PDF, EPUB and Kindle. Book excerpt: The game of Cops and Robbers is a pursuit-evasion game played on graphs with two players, the cops and the robber, who take turns moving on the graph. In each turn, they may move to a vertex adjacent to their current position or stay where they are. The cops' objective is to get to the same position where the robber is, which we refer to as to capture the robber, and the robber's goal is to evade capture indefinitely. The basic question is to find the minimum number of cops that can guarantee capturing the robber in a given graph. A very fruitful research area has been developed around the idea of modifying the way in which the cops or the robber move and analysing how these changes affect the strategies and outcome of the game. In this thesis we will study the game when we impose additional speed restrictions on the players, variants of the game popularly known as "lazy-cops and robbers" and "active cops and robbers". In order to do so, we introduce the concept of the wide shadow, aiming to improve known results and obtain new tools and techniques which may provide further insight into other open problems in the area.