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

^*Corresponding author for this work

Institute of Discrete Mathematics (5050)

Research output: Working paper › 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)

Original language	English
Number of pages	18
Publication status	Published - 1 Oct 2020

ASJC Scopus subject areas

Mathematics(all)

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Access to Document

http://arxiv.org/abs/2009.14746Licence: Unspecified

Cite this

@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)

Access to Document

Other files and links

Cite this