Travelling salesman paths on Demidenko matrices

Eranda Dragoti-Cela; Vladimir Deineko; Gerhard Woeginger

Travelling salesman paths on Demidenko matrices

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

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Diskrete Mathematik (5050)

Publikation: Arbeitspapier › Discussion paper

Abstract

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman islooking for the shortest Hamiltonian path through a set ofncities. The salesman hasto start his journey at a given citys, visit every city exactly once, and finally end histrip at another given cityt.In this paper we identify a new polynomially solvable case of the Path-TSP wherethe distance matrix of the cities is a so-called Demidenko matrix. We identify a numberof crucial combinatorial properties of the optimal solution, and we design a dynamicprogram with time complexityO(n6)

Originalsprache	englisch
Seitenumfang	18
Publikationsstatus	Veröffentlicht - 1 Okt. 2020

ASJC Scopus subject areas

Allgemeine Mathematik

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Zugriff auf Dokument

http://arxiv.org/abs/2009.14746Lizenz: Nicht definiert

Andere Dateien und Links

http://arxiv.org/abs/2009.14746

1 Artikel

Travelling salesman paths on Demidenko matrices
Dragoti-Cela, E., Woeginger, G. J. & Deineko, V., 10 Dez. 2021, (Elektronische Veröffentlichung vor Drucklegung.) in: Discrete Applied Mathematics. 12 S.
Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

Open Access

Dieses zitieren

@techreport{0de72800eb60405eb04208e90e1280f0,

title = "Travelling salesman paths on Demidenko matrices",

abstract = "In the path version of the Travelling Salesman Problem (Path-TSP), a salesman islooking for the shortest Hamiltonian path through a set ofncities. The salesman hasto start his journey at a given citys, visit every city exactly once, and finally end histrip at another given cityt.In this paper we identify a new polynomially solvable case of the Path-TSP wherethe distance matrix of the cities is a so-called Demidenko matrix. We identify a numberof crucial combinatorial properties of the optimal solution, and we design a dynamicprogram with time complexityO(n6)",

author = "Eranda Dragoti-Cela and Vladimir Deineko and Gerhard Woeginger",

year = "2020",

month = oct,

day = "1",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Travelling salesman paths on Demidenko matrices

AU - Dragoti-Cela, Eranda

AU - Deineko, Vladimir

AU - Woeginger, Gerhard

PY - 2020/10/1

Y1 - 2020/10/1

N2 - In the path version of the Travelling Salesman Problem (Path-TSP), a salesman islooking for the shortest Hamiltonian path through a set ofncities. The salesman hasto start his journey at a given citys, visit every city exactly once, and finally end histrip at another given cityt.In this paper we identify a new polynomially solvable case of the Path-TSP wherethe distance matrix of the cities is a so-called Demidenko matrix. We identify a numberof crucial combinatorial properties of the optimal solution, and we design a dynamicprogram with time complexityO(n6)

AB - In the path version of the Travelling Salesman Problem (Path-TSP), a salesman islooking for the shortest Hamiltonian path through a set ofncities. The salesman hasto start his journey at a given citys, visit every city exactly once, and finally end histrip at another given cityt.In this paper we identify a new polynomially solvable case of the Path-TSP wherethe distance matrix of the cities is a so-called Demidenko matrix. We identify a numberof crucial combinatorial properties of the optimal solution, and we design a dynamicprogram with time complexityO(n6)

UR - http://arxiv.org/abs/2009.14746

M3 - Discussion paper

BT - Travelling salesman paths on Demidenko matrices

ER -

Travelling salesman paths on Demidenko matrices

Abstract

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Publikationen

Travelling salesman paths on Demidenko matrices

Dieses zitieren