On the complexity of connection games
From MaRDI portal
Publication:307770
DOI10.1016/J.TCS.2016.06.033zbMath1371.91027arXiv1605.04715OpenAlexW2397940737MaRDI QIDQ307770
Abdallah Saffidine, Édouard Bonnet, Florian Jamain
Publication date: 5 September 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.04715
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)
Related Items (4)
Havannah and TwixT are PSPACE-complete ⋮ The maker-maker domination game in forests ⋮ The largest connected subgraph game ⋮ The largest connected subgraph game
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized pursuit-evasion games
- Graph minors. III. Planar tree-width
- Strong computational lower bounds via parameterized complexity
- Hex ist Pspace-vollständig. (Hex is Pspace-complete)
- On the complexity of some two-person perfect-information games
- The Othello game on an \(n\times n\) board is PSPACE-complete
- Finding all solutions and instances of Numberlink and Slitherlink by ZDDs
- Hex and combinatorics
- On the fairness and complexity of generalized \(k\)-in-a-row games
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- Improving Monte–Carlo Tree Search in Havannah
- Deciding first-order properties of locally tree-decomposable structures
- Dead Cell Analysis in Hex and the Shannon Game
- Parameterized Chess
- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
- GO Is Polynomial-Space Hard
- A Combinatorial Problem Which Is Complete in Polynomial Space
- Parameterized Algorithms
- A hierarchical approach to computer Hex
This page was built for publication: On the complexity of connection games
