Parameterized pursuit-evasion games

DOI10.1016/j.tcs.2010.07.004zbMath1198.91045OpenAlexW2009450360MaRDI QIDQ604466

Ulrike Stege, Allan Scott

Publication date: 11 November 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.07.004

zbMATH Keywords

parameterized complexitycops and robberalgorithmic combinatorial game theory

Mathematics Subject Classification ID

Games involving graphs (91A43) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

On the complexity of connection games, Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game, Formulation of a cooperative-confinement-escape problem of multiple cooperative defenders against an evader escaping from a circular region

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of pursuit on a graph
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• A short note about pursuit games played on a graph with a given genus
• Graph searching and a min-max theorem for tree-width
• Vertex-to-vertex pursuit in a graph
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Parametrized complexity theory.