Finding longest paths in hypercubes
MetadataShow full item record
Since 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.