SHARCNET Cloud will be powered off and decommissioned on June 1, 2021, are you ready?
SIGN-IN

Publication: Snakes, coils, and single-track circuit codes with spread k

All || By Area || By Year

Title Snakes, coils, and single-track circuit codes with spread k
Authors/Editors* Simon Hood, Daniel Recoskie, Joe Sawada, Dennis Wong
Where published* Journal of Combinatorial Optimization
How published* Journal
Year* 2013
Volume
Number
Pages 21
Publisher Springer
Keywords Snake, Coil, Circuit code, Single-track, Snake-in-the-box, Longest path
Link
Abstract
The snake-in-the-box problem is concerned with finding a longest induced path in a hypercube Q_n. Similarly, the coil-in-the-box problem is concerned with finding a longest induced cycle in Q_n.We consider a generalization of these problems that considers paths and cycles where each pair of vertices at distance at least k in the path or cycle are also at distance at least k in Q_n. We call these paths k-snakes and the cycles k-coils. The k-coils have also been called circuit codes. By optimizing an exhaustive search algorithm, we find 13 new longest k-coils, 21 new longest k-snakes and verify that some of them are optimal. By optimizing an algorithm by Paterson and Tuliani to find single-track circuit codes, we additionally find another 8 new longest k-coils. Using these k-coils with some basic backtracking, we find 18 new longest k-snakes.
Go to Combinatorial Algorithms
Back to page 1 of list