New Bounds for the Snake-in-the-Box Problem

Allison, D.; Paulusma, D.

Abstract

The Snake-in-the-Box problem is that of finding a longest induced path in an n-dimensional hypercube. We prove new lower bounds for the values n ∈ {11, 12, 13}. The Coil-in-the-Box problem is that of finding a longest induced cycle in an n-dimensional hypercube. We prove new lower bounds for the values n ∈ {10, 11, 12, 13}.

Citation

Allison, D., & Paulusma, D. (2019). New Bounds for the Snake-in-the-Box Problem. [No known commissioning body]

• Report Type: Technical Report
• Online Publication Date: Sep 24, 2019
• Publication Date: Sep 24, 2019
• Deposit Date: Sep 24, 2019
• Publicly Available Date: Oct 4, 2019
• Publisher: Durham University
• Additional Information: Publisher: Durham University; Type: monograph; Subtype: working_paper