|
Search: id:A099155
|
|
|
| A099155 |
|
Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem. |
|
+0
2
|
| |
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Some confusion seems to exist in the distinction between n-snakes and n-coils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called n-coil in newer notation, see Harary et al. a(8) is conjectured to be 97 by Rajan and Shende.
Longest open achordal path in n-dimensional hypercube.
|
|
REFERENCES
|
F. Harary, J. P. Hayes and H. J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic., 15 (1988) 277-289.
D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes". To appear in 18th International FLAIRS Conference, 2005.
D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Coils". Submitted to IEEE Conference on Evolutionary Computing, 2005.
|
|
LINKS
|
K. J. Kochut, Snake-In-The-Box Codes for Dimension 7, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996
Potter, W. D., R. W. Robinson, J. A. Miller, K. J. Kochut and D. Z. Redys, Using the Genetic Algorithm to Find Snake In The Box Codes, Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, pp. 421-426, Austin, Texas, 1994
Dayanand S. Rajan, Anil M. Shende, Maximal and Reversible Snakes in Hypercubes.
D. A. Casella and W. D. Potter, New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes.
|
|
EXAMPLE
|
a(3)=4: Path of a longest 3-snake starts at 000 and then visits 100 101 111 011.
a(4)=7: Path of a longest 4-snake: 0000 1000 1010 1110 0110 0111 0101 1101.
See figures 1 and 2 in Rajan-Shende.
|
|
CROSSREFS
|
Cf. A000937 = length of maximum n-coil.
Sequence in context: A102026 A103204 A017995 this_sequence A068031 A023431 A025246
Adjacent sequences: A099152 A099153 A099154 this_sequence A099156 A099157 A099158
|
|
KEYWORD
|
hard,nonn
|
|
AUTHOR
|
Hugo Pfoertner (hugo(AT)pfoertner.org), Oct 11 2004
|
|
EXTENSIONS
|
After 50, lower bounds on the next terms are 97,186,358,680,1260. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
|
|
|
Search completed in 0.002 seconds
|
