The complexity of pursuit on a graph

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

zbMATH Keywords

EXPTIME-completenessPSPACE completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (43)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The complexity of pursuit on a graph