Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem

DOI10.1007/S12532-013-0059-2MaRDI QIDQ744218zbMATH OpenOpenAlexFDO

Authors Pouya Baniasadi, Jerzy Filar, Michael Haythorpe, Serguei Rossomakhine, Vladimir Ejov

Publication date 6 October 2014

Published in Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10337

zbMATH Keywords

heuristicconnected graphpolynomial timeHamiltonian cycle problemLin-Kernighan

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Abstract: We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian Cycle Problem (HCP) in an undirected graph of order $n$. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph's edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic (SLH) uses transformations inspired by $k-$opt algorithms such as the, now classical, Lin-Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations.

Recommendations

• HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle
• Heuristic search for Hamilton cycles in cubic graphs
• scientific article; zbMATH DE number 4123549
• An algorithm for finding Hamilton paths and cycles in random graphs
• Hamiltonian cycle problem and Markov chains.

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Computer Solutions of the Traveling Salesman Problem
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem
• Graphs with exactly one hamiltonian circuit
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• The traveling salesman problem and its variations
• The traveling salesman problem for cubic graphs.
• The traveling salesman problem. A computational study.

Cited in

(12)

• HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle
• Incremental SAT-based method with native Boolean cardinality handling for the Hamiltonian cycle problem
• Change ringing and Hamiltonian cycles: the search for Erin and Stedman triples
• Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem
• Hamiltonian cycle curves in the space of discounted occupational measures
• Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
• Directed in-out graphs of optimal size
• Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem
• A transformation technique for the clustered generalized traveling salesman problem with applications to logistics
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem
• A note on using the resistance-distance matrix to solve Hamiltonian cycle problem

Describes a project that uses

Uses Software

• Concorde
• LKH
• TSPLIB

This page was built for publication: Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744218)