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

DOI10.1007/S12532-013-0059-2zbMATH Open1301.05326arXiv1902.10337OpenAlexW1986373227MaRDI QIDQ744218FDOQ744218

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)

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.

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

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.

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)

Cites Work

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

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

Uses Software

• TSPLIB
• LKH
• Concorde

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)