Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem

DOI10.1007/978-3-540-74593-8_12zbMATH Open1159.68469OpenAlexW1682147331MaRDI QIDQ3608477FDOQ3608477

Authors: Dorothea Baumeister, Jörg Rothe 

Publication date: 5 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74593-8_12

Recommendations

• Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
• On unique graph 3-colorability and parsimonious reductions in the plane

zbMATH Keywords

computational complexitycounting problemparsimonious reductiontiling of the planerotation puzzle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (4)

• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem
• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable

This page was built for publication: Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem

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