| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4656769 | Journal of Combinatorial Theory, Series B | 2015 | 20 Pages |
Abstract
We investigate the computational complexity of deciding whether k cops can capture a robber on a graph G. Goldstein and Reingold (1995) [8] conjectured that the problem is EXPTIME-complete when both G and k are part of the input; we prove this conjecture.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
William B. Kinnersley,