6 citations · 10 across the 11 of their papers we have counts for
15 papers
Accelerated Cops and Robbers
William B. Kinnersley, Nikolas Townsend
We consider a variant of Cops and Robbers in which both the cops and the robber are allowed to traverse up to edges on each of their turns, where . We give several gen…
Catching an infinitely fast robber on a grid
William B. Kinnersley, Nikolas Townsend
We consider a variant of Cops and Robbers in which the robber may traverse as many edges as he likes in each turn, with the constraint that he cannot pass through any vertex occupi…
Cops, robbers, and burning bridges
William B. Kinnersley, Eric Peterson
We consider a variant of Cops and Robbers wherein each edge traversed by the robber is deleted from the graph. The focus is on determining the minimum number of cops needed to capt…
Fully Active Cops and Robbers
Ilya Gromovikov, William B. Kinnersley, Ben Seamone
We study a variation of the classical pursuit-evasion game of Cops and Robbers in which agents are required to move to an adjacent vertex on every turn. We explore how the minimum…
Bounds on the localization number
Anthony Bonato, William B. Kinnersley
We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The correspo…
Bounds on the length of a game of Cops and Robbers
William B. Kinnersley
In the game of Cops and Robbers, a team of cops attempts to capture a robber on a graph . All players occupy vertices of . The game operates in rounds; in each round the cops…
Game Brush Number
William B. Kinnersley, Pawel Pralat
We study a two-person game based on the well-studied brushing process on graphs. Players Min and Max alternately place brushes on the vertices of a graph. When a vertex accumulates…
To catch a falling robber
William B. Kinnersley, Paweł Prałat, Douglas B. West
We consider a Cops-and-Robber game played on the subsets of an -set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one…
Cops and Robbers is EXPTIME-complete
William B. Kinnersley
We investigate the computational complexity of deciding whether k cops can capture a robber on a graph G. In 1995, Goldstein and Reingold conjectured that the problem is EXPTIME-co…
The capture time of the hypercube
Anthony Bonato, William B. Kinnersley, P. Gordinowicz +1
In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the captu…
The robber strikes back
Anthony Bonato, Stephen Finbow, Przemyslaw Gordinowicz +5
We consider the new game of Cops and Attacking Robbers, which is identical to the usual Cops and Robbers game except that if the robber moves to a vertex containing a single cop, t…
Toppling numbers of complete and random graphs
A. Bonato, W. Kinnersley, P. Pralat
We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accu…
A note on the acquaintance time of random graphs
W. Kinnersley, D. Mitsche, P. Pralat
In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time of a random graph . It is shown that asymptotically almos…
Game matching number of graphs
Daniel W. Cranston, William B. Kinnersley, Suil O. +1
We study a competitive optimization version of , the maximum size of a matching in a graph . Players alternate adding edges of to a matching until it becomes a maxima…
New results in -tone coloring of graphs
Daniel W. Cranston, Jaehoon Kim, William B. Kinnersley
A -tone -coloring of assigns to each vertex of a set of colors from so that vertices at distance share fewer than common colors. The {\it $…