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

DOI10.1007/s12532-013-0059-2zbMath1301.05326arXiv1902.10337OpenAlexW1986373227MaRDI QIDQ744218

Pouya Baniasadi, Serguei Rossomakhine, Jerzy A. Filar, Michael Haythorpe, Vladimir V. Ežov

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

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

Related Items (11)

A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ A note on using the resistance-distance matrix to solve Hamiltonian cycle problem ⋮ HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle ⋮ Reducing the generalised Sudoku problem to the Hamiltonian cycle problem ⋮ Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem ⋮ A construction for directed in-out subgraphs of optimal size ⋮ Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem ⋮ Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles ⋮ Hamiltonian cycle curves in the space of discounted occupational measures ⋮ 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

Uses Software

• TSPLIB
• LKH
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• The traveling salesman problem and its variations
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Graphs with exactly one hamiltonian circuit
• Computer Solutions of the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Algorithms and Data Structures

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