6 citations · 10 across the 11 of their papers we have counts for
5 papers · 2 filters
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…