Abstract | ||
---|---|---|
The snake-in-the-box problem asks for the maximum length of a chordless path (also called snake) in the $$n$$n-cube. A computer-aided approach for classifying long snakes in the $$n$$n-cube is here developed. A recursive construction and isomorph rejection via canonical augmentation form the core of the approach. The snake-in-the box problem has earlier been solved for $$n\\le 7$$n≤7; that work is here extended by showing that the longest snake in the 8-cube has 98 edges. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s00373-014-1423-3 | Graphs and Combinatorics |
Keywords | Field | DocType |
Canonical augmentation, Coil-in-the-box code, Induced path, Snake-in-the-box code, $$n$$n-Cube | Combinatorics,Brute-force search,Induced path,Snake-in-the-box,Mathematics,Hypercube,Recursion | Journal |
Volume | Issue | ISSN |
31 | 4 | 1435-5914 |
Citations | PageRank | References |
1 | 0.37 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Patric R. J. Östergård | 1 | 609 | 70.61 |
Ville H. Pettersson | 2 | 3 | 0.75 |