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

General Mathematics

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

Fingerprint

Travelling salesman paths on Demidenko matrices

Cite this