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).
Originalsprache | englisch |
---|---|
Seitenumfang | 12 |
Fachzeitschrift | Discrete Applied Mathematics |
DOIs | |
Publikationsstatus | Elektronische Veröffentlichung vor Drucklegung. - 10 Dez. 2021 |
ASJC Scopus subject areas
- Diskrete Mathematik und Kombinatorik
- Theoretische Informatik
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)