Sometimes travelling is easy : the master tour problem

V.G. Deineko, R. Rudolf, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    23 Citations (Scopus)
    157 Downloads (Pure)

    Abstract

    In 1975, Kalmanson proved that if the distance matrix in the travelling salesman problem (TSP) fulfills certain combinatorial conditions (that are nowadays called the Kalmanson conditions) then the TSP is solvable in polynomial time [Canad. J. Math., 27 (1995), pp. 1000--1010]. We deal with the problem of deciding, for a given instance of the TSP, whether there is a renumbering of the cities such that the corresponding renumbered distance matrix fulfills the Kalmanson conditions. Two results are derived: first, it is shown that---in case it exists---such a renumbering can be found in polynomial time. Secondly, it is proved that such a renumbering exists if and only if the instance possesses the so-called master tour property. A recently posed question by Papadimitriou is thereby answered in the negative.
    Original languageEnglish
    Pages (from-to)81-93
    JournalSIAM Journal on Discrete Mathematics
    Volume11
    Issue number1
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'Sometimes travelling is easy : the master tour problem'. Together they form a unique fingerprint.

    Cite this