Mathematics Computer Science Seminar
Benjamin Reiniger
IIT
Capture time in Cops and Robber with extra cops
Abstract: The game of Cops and Robber is played by $k$ cops and one robber, who initially place themselves on vertices of a graph, then take turns moving to adjacent vertices. The cops win when they capture the robber, and the robber wins by evading capture indefinitely. The \emph{capture time} is the minimum number of rounds that the cops need to capture the robber (who plays to survive as long as possible). I will briefly survey the known results and questions about the game, then discuss results on the capture time for various $k$ on trees, grids, hypercubes, and planar graphs. These results are joint with Bonato, P\'erez-Gim\'enez, and Pra\l{}at.
Monday October 9, 2017 at 3:00 PM in SEO 427