Hamiltonian Cycle Problem
The Hamiltonian cycle (HCP) problem is the problem of determining whether a Hamiltonian cycle (a cycle in an undirected or directed graph that visits each vertex exactly once) exists in a given graph (whether directed or undirected).
HCP is NP-complete and it is a special case of the traveling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance traveled is equal to the number of vertices.
Learning Resources:
An introduction on NP-complete Problems and the Hamiltonian Cycle Problem
Algorithms:
Snakes and Ladders algorithm v2.49 for the Hamiltonian Cycle Problem
The Hamiltonian cycle (HCP) problem is the problem of determining whether a Hamiltonian cycle (a cycle in an undirected or directed graph that visits each vertex exactly once) exists in a given graph (whether directed or undirected).
HCP is NP-complete and it is a special case of the traveling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance traveled is equal to the number of vertices.
Learning Resources:
An introduction on NP-complete Problems and the Hamiltonian Cycle Problem
Algorithms:
Snakes and Ladders algorithm v2.49 for the Hamiltonian Cycle Problem
Download links for SLH2: Windows - Linux
Related article:
Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Mathematical Programming Computation, 6(1), 55-75.
Benchmark sets:
See downloads page.
Related article:
Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Mathematical Programming Computation, 6(1), 55-75.
Benchmark sets:
See downloads page.