The complexity of node blocking for dags

DOI10.1016/j.jcta.2010.03.011zbMath1292.05185OpenAlexW2023995184MaRDI QIDQ616455

Dariusz Dereniowski

Publication date: 7 January 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2010.03.011

zbMATH Keywords

PSPACE-completenessannihilation gamenode blocking

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of pursuit on a graph
• Misère annihilation games
• PSPACE-Hardness of some combinatorial games
• Complexity of problems in games, graphs and algebraic equations
• Theory of annihilation games. I
• On the complexity of some two-person perfect-information games
• Theory of annihilation games