Sometimes travelling is easy : the master tour problem

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

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)
217 Downloads (Pure)


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
Issue number1
Publication statusPublished - 1998


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

Cite this