UNO is hard, even for a single player

DOI10.1016/j.tcs.2013.11.023zbMath1358.91031OpenAlexW2069939081MaRDI QIDQ389942

Nicholas J. A. Harvey, Yushi Uno, Takeaki Uno, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara

Publication date: 22 January 2014

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

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

zbMATH Keywords

dynamic programmingHamiltonian pathalgorithmic combinatorial game theorymathematical puzzles/games

Mathematics Subject Classification ID

Noncooperative games (91A10) Cooperative games (91A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46) Eulerian and Hamiltonian graphs (05C45)

Related Items

Parameterized edge Hamiltonicity, Hanabi is NP-hard, even for cheaters who look at their cards

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The edge Hamiltonian path problem is NP-complete
• Undirected edge geography
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• On the complexity of some two-person perfect-information games
• GO Is Polynomial-Space Hard
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A Combinatorial Problem Which Is Complete in Polynomial Space