The Library
Travelling salesman paths on Demidenko matrices
Tools
Tools
Tools
Cela, Eranda, Deineko, Vladimir G. and Woeginger, Gerhard J (2021) Travelling salesman paths on Demidenko matrices. Discrete Applied Mathematics . doi:10.1016/j.dam.2021.11.019 ISSN 0166-218X. (In Press)
|
PDF
1-s2.0-S0166218X21004716-main.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (831Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-travelling-salesman-paths-Demidenko-matrices-Deineko-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (662Kb) |
Official URL: https://doi.org/https://doi.org/10.1016/j.dam.2021...
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).
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Computational complexity, Hamiltonian systems | ||||||||||||
| Journal or Publication Title: | Discrete Applied Mathematics | ||||||||||||
| Publisher: | Elsevier Science Ltd. | ||||||||||||
| ISSN: | 0166-218X | ||||||||||||
| Official Date: | 10 December 2021 | ||||||||||||
| Dates: |
|
||||||||||||
| DOI: | 10.1016/j.dam.2021.11.019 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | In Press | ||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
| Date of first compliant deposit: | 29 November 2021 | ||||||||||||
| Date of first compliant Open Access: | 13 December 2021 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
