Finding a Hamiltonian Path in a Cube with Specified Turns is Hard

Finding a Hamiltonian Path in a Cube with Specified Turns is Hard

We prove the NP-completeness of finding a Hamiltonian path in an N × N × N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N3 unit cubes, joined at face centers (usually by a cord passing through all...

Full description

Bibliographic Details
Main Authors: Abel, Zachary Ryan, Demaine, Erik D., Demaine, Martin L., Eisenstat, Sarah Charmian, Lynch, Jayson R., Schardl, Tao Benjamin
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Information Processing Society of Japan 2014
Online Access:http://hdl.handle.net/1721.1/86227
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-4295-1117
https://orcid.org/0000-0002-3182-1675
https://orcid.org/0000-0003-0198-3283

Internet

http://hdl.handle.net/1721.1/86227
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-4295-1117
https://orcid.org/0000-0002-3182-1675
https://orcid.org/0000-0003-0198-3283

Similar Items