Name
Abstract | ||
|---|---|---|
A robber and k cops choose starting vertices in a graph and move in alternation from vertex to vertex along the edges of the graph; capture occurs if a cop ever shares a vertex with the robber. If k is not fixed and if either the graph is directed or initial positions are given, we show that the problem is EXPTIME-complete. Similar techniques lead to the PSPACE- and EXPTIME-completeness of some other combinatorial games that were previously only known to be NP- and PSPACE-hard. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0304-3975(95)80012-3 | Theoretical Computer Science |
Keywords | DocType | Volume |
combinatorial games | Journal | 143 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 48 |
PageRank | References | Authors |
3.52 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arthur S. Goldstein | 1 | 82 | 6.72 |
| Edward M. Reingold | 2 | 2214 | 563.65 |