TY - JOUR

T1 - Sometimes travelling is easy : the master tour problem

AU - Deineko, V.G.

AU - Rudolf, R.

AU - Woeginger, G.J.

PY - 1998

Y1 - 1998

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

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

U2 - 10.1137/S0895480195281878

DO - 10.1137/S0895480195281878

M3 - Article

SN - 0895-4801

VL - 11

SP - 81

EP - 93

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -