Snakes and Ladders Heuristic – Web Interface
SLHWeb is designed to find Hamiltonian cycles in large connected graphs. The interface is powered by the Snakes and Ladders Heuristic. SLHWeb has a large number of graphs built in which serve as a demonstration of the potency of the Snakes and Ladders Heuristic. Where possible, a reference has been given for the included graphs at the bottom of this page. Alternatively, you can submit your own graph (in edge-list format) to solve via SLH.
There are two solving options – Start SLH and Start slow SLH. Start SLH will run SLH in real time, updating the animation as often as possible. However, note that the solving time may be slowed down if there is a heavy load on the server, and may not reflect the true solving time of SLH. Start slow SLH is a staggered version of the Snakes and Ladders Heuristic, where the speed of execution is adjustable.
SLHWeb requires Java Runtime Environment to run. You can download JRE here.
If you have any questions about SLHWeb, please contact Michael Haythorpe.
Snakes and Ladders Heuristic developed by:
Pouya Baniasadi
Vladimir Ejov
Jerzy Filar
Michael Haythorpe
Serguei Rossomakhine
Snakes and Ladders Heuristic coded by:
Serguei Rossomakhine
SLHWeb coded by:
Kieran Clancy
Michael Haythorpe
References for included graphs:
Foster Graph: Symmetric Cubic Graph F090 from The Foster Census [1]
Biggs-Smith Graph: Distance-regular Symmetric Cubic Graph F090 from The Foster Census [1]
Knights Tour Problems: Non-regular graphs arising from the path of a knight on chessboard of arbitrary size [2]
TSPLIB Graphs: HCP instances provided by University of Heidelberg [3]
Generalized Petersen Graphs: Graphs GP(n,2) have only three Hamiltonian cycles whenever n = 3 mod 6 [4]
Sheehan Graphs: These graphs have the largest number of edges possible while containing only a single Hamiltonian cycle [5]
FHCP Challenge Set: Difficult instances from a set of 1001 graph produced by FHCP. Available here.
[1] Bouwer, I.Z., Chernoff, W.W., Monson, B. and Star, Z. The Foster Census. Charles Babbage Research Centre, 1988.
[2] Weisstein, Eric W. Knight Graph. From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/KnightGraph.html
[3] TSPLIB, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[4] Coxeter, H.S.M. Self-Dual Configurations and Regular Graphs. Bulletin of American Mathematics Society, 56:413-455, 1950.
[5] Sheehan, J. Graphs with exactly one hamiltonian circuit. Journal of Graph Theory, 1:37-43, 1977.