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

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

Jerzy A. Filar, Michael Haythorpe, Serguei Rossomakhine, Pouya Baniasadi, 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

heuristic; connected graph; polynomial time; Hamiltonian cycle problem; Lin-Kernighan

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

05C45: Eulerian and Hamiltonian graphs

Uses Software

• TSPLIB
• LKH
• Concorde