Tetravex is NP-complete

DOI10.1016/J.IPL.2006.04.010zbMath1185.68354DBLPjournals/ipl/TakenagaW06OpenAlexW2136889863WikidataQ57481109 ScholiaQ57481109MaRDI QIDQ845713

Toby Walsh, Yasuhiko Takenaga

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.04.010

zbMATH Keywords

computational complexityNP-completenesstetravex

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Recent results on Douglas-Rachford methods for combinatorial optimization problems ⋮ \textsc{Hanano} puzzle is \textsf{NP}-hard ⋮ On the hardness of solving edge matching puzzles as SAT or CSP problems

Cites Work

• The \((n^ 2-1)\)-puzzle and related relocation problems
• It is tough to be a plumber
• Tetris is Hard, Even to Approximate

This page was built for publication: Tetravex is NP-complete