References

There have been publications on the snake-in-the-box problem for over 50 years now. This page provides you with almost all the major references available, including the first paper ever, on this problem.

• Abbott, H.L., and Katchalski, M., "On the Snake-in-the-Box Problem", J. Combin. Theory, Vol. 45, pp 13-24, 1988.

• Abbott, H.L., and M. Katchalski, "Snakes and Pseudo-Snakes in Powers of Complete Graphs", Discrete Mathematics, Vol. 68, pp 1-8, 1988.

• Abbott, H.L., and Katchalski, M., "Further Results on Snakes in Powers of Complete Graphs", Discrete Mathematics, Vol. 91, pp 111-120, 1991.

• Abbott, H.L., and Katchalski, M., "On the Construction of Snake in the Box Codes", Utilitas Mathematica, Vol. 40, pp 97-116, 1991.

• Abbott, H.L., and Katchalski, M., "Estimates for Snakes and Pseudo-Snakes in k_n^d ", Utilitas Mathematica, Vol. 43, pp 97-100, 1993.

• Adelson, L.E., Alter, R.,and Curtz, T.B., "Long snakes and a characterization of maximal snakes on the d-cube", in the Proceedings of 4th SouthEastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 8, pp 111-124, 1973.

• Axenovich, M., and Martin, R., "A note on short cycles in a hypercube", Discrete Math. Vol. 306, pp 2212-2218, 2006.

• Bishop, J., "Investigating the Snake-in-the-box problem with Neuroevolution", Department of Comp. Sci., University of Texas, Austin.

• Black W. L., "Electronic combination locks", Quart. Progress Report of the Research Laboratory of Electronics, No. 73, Massachusetts Institute of Technology, Cambridge, Massachusetts, pp 232-233, April, 1964.

• Blass, U., Honkala, I., Karpovsky, M., and Litsyn, S., "Short dominating paths and cycles in the binary hypercube", Ann. Combin, Vol. 5, pp 51–59, 2001.

• Carlson, B.P., "Rule Coding for Genetic Algorithms: An Alternative Solution to the Traveling Salesman Problem", in the Proceedings of the Inter. Conf. on Artificial Intelligence, Las Vegas, NV, pp 878-883, June, 2002.

• Carlson, B.P., and Hougen D., "Phenotype Feedback Genetic Algorithm Operators for Heuristic Encoding of Snakes and Hypercubes", in the Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO '10, pp 791-798, Portland, Oregon, USA, July 07 - 11, 2010.

• Casella, D.A., and Potter, W.D., "New Lower Bounds for the Coil-In-The-Box Problem: Using Evolutionary Techniques to Hunt for Coils", in the Proceedings of the International Conference on Computational Intelligence, Man-Machine Systems, and Cybernetics, CIMMACS’05, CD Proceedings Paper No. 501-111, Miami, Florida, November 17-19, 2005.

• Casella, D.A., and Potter, W.D., "Using Evolutionary Techniques to Hunt for Snakes and Coils", in the Proceedings of 2005 IEEE Congress on Evolutionary Computing, CEC’05, pp 2499-2505, Edinburgh, Scotland, September 2-5, 2005.

• Casella, D.A., and Potter, W.D., "New Lower Bounds for the Snake-In-The-Box Problem: Using Evolutionary Techniques to Hunt for Snakes", in Proceedings of the 18th International FLAIRS Conference, pp 264-269, Clearwater Beach, Florida, May, 2005.

• Chebiryak, Y., Kroening, D, "An efficient SAT encoding of circuit snakes", in Proceedings of IEEE International Symposium on Information Theory and its Applications, Auckland, New Zealand, pp 1235–1238, December 7-10, 2008.

• Chebiryak, Y., Wahl, T., Kroening, D., and Haller, L., "Finding Lean Induced Cycles in Binary Hypercubes", in Proceedings of SAT Conference, Lecture Notes in Computer Science no. 5584, Springer Verlag, pp 18-31, June, 2009.

• Chien, R.T., Freiman, C.V., and Tang, D.T., "Error connection and circuits on the n-cube", in the Proceedings of the 2nd Allerton Conference on Circuit and System Theory, Univ of Illinois, Monitcello, Illinois, pp 899-912, September 28-30, 1964.

• Danzer, L., and Klee, V., "Lengths of Snakes in Boxes", J. Combinatorial Theory, Vol. 2, pp 258-265, 1967.

• Davies, D.W., "Longest -Separated- Paths and Loops in an N Cube", IEEE Trans. Electronic Computers, Vol. 14, p. 261, 1965.

• Deimer, K., "Some new bounds for the maximum length of circuit codes", IEEE Transactions on Information Theory, Vol. 30, pp 754-756, 1984.

• Deimer, K., "A New Upper Bound for the Length of Snakes", Combinatorica, Vol. 5(2), pp 109-120, 1985.

• Diaz-Gomez, P., and Hougen, D., "Genetic algorithms for hunting snakes in hypercubes: fitness function analysis and open questions", in Seventh ACIS Intern Conf on Softw Eng, Artif Intell, Netw, and Parallel/Distrib Comput (SNPD’06). IEEE, Computer Society, Los Alamitos CA, pp 389-394, 2006.

• Diaz-Gomez, P., and Hougen, D., "The snake in the box problem: Mathematical Conjecture and a Genetic Algorithm Approach", In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (Seattle, Washington, USA, July 08 - 12, 2006). GECCO '06. ACM, New York, NY, pp 1409-1410.

• Dixon, E., and Goodman, S., "On the Number of Hamilton Circuits in the n-Cube", in the Proceedings of the American Mathematical Society, Vol. 50, pp 500-504, July, 1975.

• Dontas, K, and De Jong, K., "Discovery of maximal distance codes using Genetic Algorithm", in the  Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, pp 805- 811, 1990.

• Douglas, R.J., "Some results on the Maximum Length of Circuits of Spread k in the d-Cube", J. Combin. Theory, Vol. 6, pp 323-339, 1969.

• Douglas, R.J., "Upper Bounds on the lengths of circuits of even spread in the d-cube", J. Combin. Theory, Vol. 7, pp 206-214, 1969.

• Emelyanov, P.G., and Lukito, A., "On the maximal length of a snake in hypercubes of small dimension", in Discrete Mathematics, Vol. 218, pp 51-59, 2000.

• Etzion, T., and  Paterson, K.G., "Near optimal single-track Gray codes", in IEEE Transactions on Information Theory, Vol. 42, pp 779-789, 1996.

• Evdokimov, A.A., “Maximal length of a chain in a unit n-dimensional cube”, Mat. Zametki, Vol. 6, pp 306-319, 1969.

• Even, S., "Snake in the Box Codes", correspondence in IRE Transactions on Electronic Computers, Vol. EC-12, p. 18, 1963.

• Harary, F., Hayes, J.P., and Wu, H.J., "A survey of the theory of hypercube graphs", Comput. Math. Applic., Vol. 15, pp 277-289, 1988.

• Haryanto, L., and van Zanten, A.J., "Snake-in-the-box codes and Euclidean Geometries", in Proceedings of the Ninth International Workshop ACCT, Kranevo, Bulgaria, pp 208–213, June, 2004.

• Haryanto, L., "Constructing Snake-In-The-Box Codes and Families of such Codes Covering the Hypercube", Ph.D. Dissertation (A.J. van Zanten, advisor), Delft University of Technology, Delft, the Netherlands, 2007.

• Hiltgen, A.P., and Paterson K.G., "Single Track Circuit Codes", IEEE Transactions on Information Theory, Vol. 47, pp 2587-2595, 2000.

• Juric, M., Potter, W.D., and Plaksin, M., "Using PVM for Hunting Snake In The Box Codes", Proceedings of the 1994 Transputer Research and Applications Conference (NATUG-7), pp 97-102, Athens, GA, October, 1994.

• Kautz, W.H., "Unit-Distance Error-Checking Codes", IRE Trans. Electronic Computers, Vol. 7, pp 179-180, 1958.

• Kim, S., and Neuhoff, D.L., “Snake-in-the-box codes as robust quantizer index assignments”, in Proceedings of IEEE International Symposium on Information Theory, p 402, June 25-30, 2000.

• Kinny, D., "A New Approach to the Snake-In-The-Box Problem", European Conference on Artificial Intelligence, Montpellier, France, pp 462-467, 2012.

• Klee, V., "A method for constructing circuit codes", J. Assoc. Comput. Mach., Vol. 14, pp 520-538, 1967.

• Klee, V., "What is the maximum length of a d-dimensional snake?", Amer. Math. Monthly, Vol. 77, pp 63-65, 1970.

• Klee, V., "The Use of Circuit Codes in Analog-to-Digital Conversion", Graph Theory and its Applications (B.Harris, ed.), Academic Press, New York, pp 121-131, 1970.

• Kochut, K.J., "Snake-in-the-box codes for dimension 7", J Comb Math Comb Comput, Vol. 20, pp 175-185, 1996.

• Krafka, K.J., "The Snake-in-the-Box Problem", ACMSE '10, Oxford, MS, USA, April 15-17, 2010.

• Lukito, A., and van Zanten, A.J., "A new non-asymptotic upper bound for snake-in-the-box codes", in Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 39, pp 147-156, 2001.

• Lukito, A., and van Zanten, A.J., "Vertex Partitions of Hypercubes into Symmetric Snakes", Electronic Notes in Discrete Mathematics, Vol. 11, pp 459-467, 2002.

• Palani, A., and Potter, W.D., "Hypercube Snake-In-The-Box Exploration Using Level Representation", in the Proceedings of the 18th IMACS World Congress on Computational and Applied Mathematics & Applications in Science and Engineering, Athens, Georgia, August, 2009 (to appear).

• Paterson, K.G. and Tuliani, J., "Some New Circuit Codes", IEEE Transactions on Information Theory, Vol. 44(3), pp 1305-1309, 1998.

• Potter, W.D., Robinson R.W., Miller J.A., and Kochut, K.J., "Using the Genetic Algorithm to Find Snake- In-The-Box Codes", In Proc of the 7th International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, pp 421-426. Austin, Texas, 1994.

• Preparata, F., and  Nievergelt, J.,  "Difference-preserving codes", IEEE Transactions on Information Theory, Vol. 20, pp 643-649, 1974.

• Rajan D.S.,  and Shende A.M., "Maximal and Reversible Snakes in the Hypercube", in Proceedings of the Annual Australian Conference on Combinatorial Mathematics and Combinatorial Computing, 1999.

• Ramanujacharyulu, C., and Menon, V.V., "A note on the snake-in-the-box problem", Publ. Inst. Statist. Univ. Paris 13 , pp 131–135, 1964.

• Rickabaugh, B.P., and Shende, A.M., "Using PVM to Hunt Maximal Snakes in Hypercubes", Journal of Computing in Small Colleges Volume 14 (2), pp 76-84, 1998.

• Shende, A.M., "Searching for Patterns of Snakes in Hypercubes", Journal of Computing Sciences in Colleges Volume 16 (2), pp 168-176, 2001.

• Singleton, R.C., "Generalized Snake-in-the-Box Codes", IEEE Trans. Electronic Computers, Vol. 15, pp 596-602, 1966.

• Smith, B.A., "A Survey of Approaches to Snake-in-the-Box Construction", Technical Report, University of Georgia, 2006.

• Snevily, H.S., "The Snake-in-the-Box Problem: A New Upper Bound", Discrete Math, vol. 133, pp 307–314, 1994.

• Solov’jeva, F.I., "An Upper Bound for the Length of a Cycle in an n-Dimensional Unit Cube", Discret. Analiz., Vol. 45, pp 71-76, 1987. [English Translation]

• Tuohy D.R., Potter, W.D., and Casella, D.A., "Searching for snake-in-the-box codes with evolved pruning models", In: Arabnia HR, Yang JY, Yang MQ (eds) Proc 2007 Int Conf Genet and Evol Methods (GEM’2007). CSREA Press, pp 3-9, 2007.

• Vasil’ev, Ju. I., "On the length of a cycle in an n-dimensional unit cube", Soviet Math. Dokl., Vol. 4, pp 160-163, 1963.

• Wang, L., and Potter, W.D., "SIB Code Search Based on Temporal Difference Learning", in the Proceedings of the 18th IMACS World Congress on Computational and Applied Mathematics & Applications in Science and Engineering, Athens, Georgia, August, 2009 (to appear).

• Wojciechowski, J., "A new lower bound for Snake-in-the-Box codes", Combinatorica, Vol. 9, pp 91-99, 1989.

• Wojciechowski, J., "Covering the Hypercube with a Bounded Number of Disjoint Snakes", Combinatorica, Vol. 14, pp 1-6, 1994.

• Wojciechowski, J., "Long Snakes in Powers of the Complete Graph With an Odd Number of Vertices", Journal of London Mathematical Society, Vol. 50 (3), pp 465-476, 1994.

• Wojciechowski, J., "On the Length of Snakes in Powers of Complete Graphs", J. London Math. Soc., Vol. 71 (1), pp 22-32, 2005.

• Wong, C., and Sawada, J.,"Exhaustive Search for Maximal Length Coil-In-The-Box Codes", University of Guelph Technical Report (TR-UG-CIS-2008-001), Guelph, Ontario, Canada, June, 2008.

• Wyner, A.D., "Note on Circuits and Chains of Spread k in the n-Cube", IEEE Transactions on Computers, Vol. 20 (4), p. 474, April, 1971.

• Yehezkeally, Y., and Schwartz, M.,"Snake-in-the-Box Codes for Rank Modulation", Submitted: http://arxiv.org/abs/1107.3372v1

• van Zanten, A.J., and Haryanto, L., "Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube", in Designs, Codes, and Cryptography, Vol. 48, pp 207-229, 2008.

• van Zanten, A.J., and Lukito, A., "Construction of Certain Cyclic Distance-Preserving Codes Having Linear-Algebraic Characteristics", Designs, Codes, and Cryptography, Vol. 16 (2), pp 185-199, 1999.

• Zemor, G., "An Upper Bound on the Size of the Snake-In-The-Box", in Combinatorica, Vol. 17 (2), pp 287-298, 1997.

• Zinovik, I., Chebiryak, Y., and Kroening, D.,"Periodic Orbits and Equilibria in Glass Models for Gene Regulatory Networks", IEEE Transactions on Information Theory, Vol. 56 (2), p. 805-820, February, 2010.

 

MS Theses

• Xianjuan Lu, "Hunting for Snakes Using Simulated Annealing", 1994.

• Scott Bitterman, "New Lower Bounds for the Snake-In-The-Box Problem : a Prolog Genetic Algorithm and Heuristic Search Approach", 2004.

• Darren Casella, "New Lower Bounds for the Snake-In-The-Box Problem : Using Evolutionary Techniques to Hunt for Snakes and Coils", 2005.

• Shilpa Hardas, "An Ant Colony Approach to the Snake-in-the-Box Problem", 2005.

• Chris Taylor, "A Comprehensive Framework for the Snake-in-the-Box Problem", 2007.

• Eric Drucker, "Exploring Applications of External Optimization", 2009.