Travelling salesman paths on Demidenko matrices

Eranda Dragoti-Cela*, Gerhard J. Woeginger, Vladimir Deineko

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract


In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s, visit every city exactly once, and finally end his trip at another given city t.
In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O(n6).
Original languageEnglish
Number of pages12
JournalDiscrete Applied Mathematics
DOIs
Publication statusE-pub ahead of print - 10 Dec 2021

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Basic - Fundamental (Grundlagenforschung)

Cite this