On the computational complexities of various geography variants

DOI10.1016/j.dam.2022.02.016zbMath1489.91055arXiv2108.09367OpenAlexW3194408827MaRDI QIDQ2127615

Carson Geissler, Nathan Fox

Publication date: 20 April 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.09367

zbMATH Keywords

computational complexitycombinatorial gamesPSPACE-completegeneralized geography

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undirected edge geography
• Geography
• Complexity of path-forming games
• On the complexity of some two-person perfect-information games
• On variants of vertex geography on undirected graphs
• The Shortest Path Game: Complexity and Algorithms
• GO Is Polynomial-Space Hard
• Reducibility among Combinatorial Problems

This page was built for publication: On the computational complexities of various geography variants