| Article ID: | iaor20001850 |
| Country: | United Kingdom |
| Volume: | 26 |
| Issue: | 4 |
| Start Page Number: | 353 |
| End Page Number: | 369 |
| Publication Date: | Apr 1999 |
| Journal: | Computers and Operations Research |
| Authors: | Kabadi Santosh N., Baki Md. Fazle |
| Keywords: | heuristics |
In this paper, we give new polynomially testable sufficiency conditions for a given instance of the traveling salesman problem (TSP) to have an optimal tour that is pyramidal. This properly generalizes the Demidenko condition and the conditions of Warren. We thus have new, nontrivial polynomially testable and polynomially solvable cases of TSP.