A note on using the resistance-distance matrix to solve hamiltonian cycle problem

V Ejov, J Filar, M Haythorpe, J Roddick, S Rossomakhine

    Research output: Contribution to journalArticle

    1 Citation (Scopus)

    Abstract

    An instance of Hamiltonian cycle problem can be solved by converting it to an instance of Travelling salesman problem, assigning any choice of weights to edges of the underlying graph. In this note we demonstrate that, for difficult instances, choosing the edge weights to be the resistance distance between its two incident vertices is often a good choice. We also demonstrate that arguably stronger performance arises from using the inverse of the resistance distance. Examples are provided demonstrating benefits gained from these choices.

    Original languageEnglish
    Pages (from-to)393-399
    Number of pages7
    JournalAnnals of Operations Research
    Volume261
    Issue number1-2
    DOIs
    Publication statusPublished - 1 Jan 2018

    Fingerprint Dive into the research topics of 'A note on using the resistance-distance matrix to solve hamiltonian cycle problem'. Together they form a unique fingerprint.

  • Cite this