The complexity of pursuit on a graph
From MaRDI portal
Publication:673639
DOI10.1016/0304-3975(95)80012-3zbMath0873.68152OpenAlexW2013405119MaRDI QIDQ673639
Arthur S. Goldstein, Edward M. Reingold
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)80012-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Variations on cops and robbers, Cops and robber on butterflies and solid grids, Traveling salesmen in the presence of competition, Complexity, appeal and challenges of combinatorial games, Unnamed Item, Fast Robber in Planar Graphs, The lion and man game on polyhedral surfaces with obstacles, Cops and robbers on intersection graphs, Cops and robbers from a distance, Parameterized pursuit-evasion games, The guarding game is E-complete, The complexity of node blocking for dags, Visibility graphs, dismantlability, and the cops and robbers game, Cops and robber on oriented graphs with respect to push operation, Smarter Lions: Efficient Cooperative Pursuit in General Bounded Arenas, Cops that surround a robber, A note on \(k\)-cop, \(l\)-robber games on graphs, Collaborative pursuit-evasion strategy of UAV/UGV heterogeneous system in complex three-dimensional polygonal environment, Static and expanding grid coverage with ant robots: complexity results, To satisfy impatient web surfers is hard, The one-cop-moves game on graphs with some special structures, Guard games on graphs: keep the intruder out!, How to guard a graph?, Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem, The role of information in the cop-robber game, An annotated bibliography on guaranteed graph searching, Fine-grained Lower Bounds on Cops and Robbers, Cops and robber on some families of oriented graphs, Escaping offline searchers and isoperimetric theorems, Cops and robber game without recharging, Cops and robbers is EXPTIME-complete, Pursuing a fast robber on a graph, Bounds for cops and robber pursuit, Bounds on the length of a game of cops and robbers, Large classes of infinite k-cop-win graphs, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs, Variations of cops and robbers game on grids, A two-person game on graphs where each player tries to encircle his opponent's men, Linguistic geometry approach for solving the cops and robber problem in grid environments, The capture time of a graph, Recent results and questions in combinatorial game complexities, Conjectures on Cops and Robbers
Cites Work
- A game of cops and robbers
- Note on a pursuit game played on graphs
- The complexity of two-player games of incomplete information
- A short note about pursuit games played on a graph with a given genus
- PSPACE-Hardness of some combinatorial games
- On a pursuit game on Cayley graphs
- Cops and robbers in graphs with large girth and Cayley graphs
- On a pursuit game on Cayley digraphs
- On a pursuit game played on graphs for which a minor is excluded
- Complexity of problems in games, graphs and algebraic equations
- Theory of annihilation games. I
- On a game of policemen and robber
- Vertex-to-vertex pursuit in a graph
- Complexity of Finding Embeddings in a k-Tree
- Some combinatorial game problems require Ω( n k ) time
- The complexity of searching a graph
- Provably Difficult Combinatorial Games
- Classes of Pebble Games and Complete Problems
- Alternation
- On Hamiltonian Regular Graphs of Girth Six
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
