Pyramidal traveling salesman problem

Authors
Baki, MF Kabadi, SN
Citation
Mf. Baki et Sn. Kabadi, Pyramidal traveling salesman problem, COMPUT OPER, 26(4), 1999, pp. 353-369
Citations number
8
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
26
Issue
4
Year of publication
1999
Pages
353 - 369
Database
ISI
SICI code
0305-0548(199904)26:4<353:PTSP>2.0.ZU;2-L
Abstract
In this paper, we give new polynomially testable sufficiency conditions for a given instance of the traveling salesman problem (TSP) to have an optima l tour that is pyramidal. This properly generalizes the Demidenko condition and the conditions of Warren. We thus have new, nontrivial polynomially te stable and polynomially solvable eases of TSP. (C) 1999 Elsevier Science Lt d. All rights reserved.