scientific article

DOI10.4134/BKMS.b190097zbMath1445.05069MaRDI QIDQ3305770

Yaroslav N. Shitov

Publication date: 12 August 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

PSPACE-completenesscop throttling number

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pursuit and evasion games (49N75) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Unnamed Item
• Cops and Robbers on diameter two graphs
• The complexity of pursuit on a graph
• Throttling for the game of cops and robbers on graphs
• Bounds on the length of a game of cops and robbers
• A game of cops and robbers
• The capture time of a graph
• Computing a perfect strategy for nxn chess requires time exponential in n
• Gobang is PSPACE-complete
• The Othello game on an \(n\times n\) board is PSPACE-complete
• A game of cops and robbers played on products of graphs
• Vertex-to-vertex pursuit in a graph
• On the computational complexity of a game of cops and robbers
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• The game of overprescribed Cops and Robbers played on graphs
• Parametrized complexity theory.
• Cops and Robbers on Graphs Based on Designs
• Cops and Robber with Constraints

This page was built for publication: