Two Dots is NP-complete

DOI10.4230/LIPICS.FUN.2016.24zbMATH Open1369.68218OpenAlexW2483065946MaRDI QIDQ5282822FDOQ5282822

Authors: Neeldhara Misra 

Publication date: 17 July 2017

Full work available at URL: https://dblp.uni-trier.de/db/conf/fun/fun2016.html#Misra16

Recommendations

• On the complexity of Two Dots for narrow boards and few colors
• Bust-a-Move/Puzzle Bobble is NP-complete
• Strategy and Complexity of The Game of Squares
• TETRIS IS HARD, EVEN TO APPROXIMATE
• scientific article; zbMATH DE number 1944412

zbMATH Keywords

puzzleNP-completeperfect informationcombinatorial game theoryTwo Dots

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cited In (8)

• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• Trainyard is NP-hard
• On the complexity of Two Dots for narrow boards and few colors
• Dots & Polygons (Media Exposition)
• Tracks from hell -- when finding a proof may be easier than checking it
• Bust-a-Move/Puzzle Bobble is NP-complete
• On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
• Tracks from hell -- when finding a proof may be easier than checking it

This page was built for publication: Two Dots is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282822)