Deterministic "snakes and Ladders" Heuristic for the Hamiltonian cycle problem

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

    Research output: Contribution to journalArticlepeer-review

    9 Citations (Scopus)

    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 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.

    Original languageEnglish
    Pages (from-to)55-75
    Number of pages21
    JournalMathematical Programming Computation
    Volume6
    Issue number1
    DOIs
    Publication statusPublished - 2014

    Keywords

    • Connected graph
    • Hamiltonian cycle problem
    • Heuristic
    • Lin-Kernighan
    • Polynomial time

    Fingerprint Dive into the research topics of 'Deterministic "snakes and Ladders" Heuristic for the Hamiltonian cycle problem'. Together they form a unique fingerprint.

    Cite this