Show simple item record

dc.contributor.authorMeyerson, Seth
dc.description.abstractSince the problem's formulation by Kautz in 1958 as an error detection tool, diverse applications for long snakes and coils have been found. These include coding theory, electrical engineering, and genetics. Over the years, the problem has been explored by many researchers in different fields using varied approaches, and has taken on additional meaning. The problem has become a benchmark for evaluating search techniques in combinatorially expansive search spaces (NP-complete Optimizations). In two papers, the second building upon the first, we present an effective process for searching longest induced paths: open (snakes), closed (coils), and symmetric closed (symmetric coils) in n-dimensional hypercube graphs. Stochastic Beam Search, a non-deterministic variant of Beam Search, provides the overall structure for our search, while graph theory based techniques are used in the computation of a generational fitness value. This novel fitness value is used in guiding the search. We present eleven new lower bounds for the Snake-in-the-Box problem for snakes in dimensions 11, 12, and 13; coils in dimensions 10, 11, and 12; and symmetric coils in dimensions 9, 10, 11, 12, and 13. The best known solutions of the unsolved dimensions of this problem have improved over the years and we are proud to make a contribution to this problem as well as the continued progress in combinatorial search techniques.
dc.subjectstochastic beam search
dc.subjectcombinatorial optimization
dc.subjectgraph search
dc.subjectheuristic search
dc.titleFinding longest paths in hypercubes
dc.title.alternative11 new lower bounds for snakes, coils, and symmetrical coils
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorWalter D. Potter
dc.description.committeeWalter D. Potter
dc.description.committeeKhaled Rasheed
dc.description.committeeKrzysztof J. Kochut

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record