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

Simon Hood (), Daniel Recoskie (), Joe Sawada () and Dennis Wong ()
Additional contact information
Simon Hood: University of Guelph
Daniel Recoskie: University of Guelph
Joe Sawada: University of Guelph
Dennis Wong: University of Guelph

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 5, 42-62

Abstract: Abstract The snake-in-the-box problem is concerned with finding a longest induced path in a hypercube $$Q_n$$ Q n . Similarly, the coil-in-the-box problem is concerned with finding a longest induced cycle in $$Q_n$$ Q n . We consider a generalization of these problems that considers paths and cycles where each pair of vertices at distance at least $$k$$ k in the path or cycle are also at distance at least $$k$$ k in $$Q_n$$ Q n . We call these paths $$k$$ k -snakes and the cycles $$k$$ k -coils. The $$k$$ k -coils have also been called circuit codes. By optimizing an exhaustive search algorithm, we find 13 new longest $$k$$ k -coils, 21 new longest $$k$$ 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$$ k -coils. Using these $$k$$ k -coils with some basic backtracking, we find 18 new longest $$k$$ k -snakes.

Keywords: Snake; Coil; Circuit code; Single-track; Snake-in-the-box; Longest path (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9630-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9630-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9630-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().