Travelling salesman paths on Demidenko matrices

Eranda Dragoti-Cela; Gerhard J. Woeginger; Vladimir Deineko

doi:10.1016/j.dam.2021.11.019

Travelling salesman paths on Demidenko matrices

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

^*Corresponding author for this work

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-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 language	English
Number of pages	12
Journal	Discrete Applied Mathematics
DOIs	https://doi.org/10.1016/j.dam.2021.11.019
Publication status	E-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)

Access to Document

10.1016/j.dam.2021.11.019Licence: CC BY 4.0

https://www.sciencedirect.com/science/article/pii/S0166218X21004716

1 Article
1 Discussion paper

Travelling salesman paths on Demidenko matrices
Çela , E., Deineko, V. & Woeginger, G. J., 15 Sept 2024, In: Discrete Applied Mathematics. 354, p. 3-14 11 p.
Research output: Contribution to journal › Article › peer-review

Open Access
Travelling salesman paths on Demidenko matrices
Dragoti-Cela, E., Deineko, V. & Woeginger, G., 1 Oct 2020, 18 p.
Research output: Working paper › Discussion paper

Cite this

@article{58ea4f36f3fe428285c12e87020297d6,

title = "Travelling salesman paths on Demidenko matrices",

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).",

author = "Eranda Dragoti-Cela and Woeginger, {Gerhard J.} and Vladimir Deineko",

year = "2021",

month = dec,

day = "10",

doi = "10.1016/j.dam.2021.11.019",

language = "English",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Travelling salesman paths on Demidenko matrices

AU - Dragoti-Cela, Eranda

AU - Woeginger, Gerhard J.

AU - Deineko, Vladimir

PY - 2021/12/10

Y1 - 2021/12/10

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

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

U2 - 10.1016/j.dam.2021.11.019

DO - 10.1016/j.dam.2021.11.019

M3 - Article

SN - 0166-218X

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Travelling salesman paths on Demidenko matrices

Abstract

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Research output