Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
The Game of Wall Cops and Robbers
verfasst von : Anthony Bonato, Fionn Mc Inerney
Erschienen in: Computational Intelligence, Cyber Security and Computational Models
Verlag: Springer Singapore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Wall Cops and Robbers is a new vertex pursuit game played on graphs, inspired by both the games of Cops and Robbers and Conway’s Angel Problem. In the game, the cops are free to move to any vertex and build a wall; once a vertex contains a wall, the robber may not move there. Otherwise, the robber moves from vertex-to-vertex along edges. The cops capture the robber if the robber is surrounded by walls. The wall capture time of a graph G, written \( W_{{c_{t} }} (G) \) is the least number of moves it takes for one cop to capture the robber in G. In the present note, we focus on the wall capture time of certain infinite grids. We give upper bounds on the wall capture time for Cartesian, strong, and triangular grids, while giving the exact value for hexagonal grids. We conclude with open problems.