Four point conditions and exponential neighborhoods for the symmetric TSP

V.G. Deineko, B. Klinz, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)


In most of the known polynomially solvable cases of the symmetric travelling salesman problem (TSP) which result from restrictions on the underlying distance matrices, the restrictions have the form of so-called four-point conditions (the inequalities involve four cities). In this paper we treat all possible (symmetric) four-point conditions and investigate whether the corresponding TSP can be solved in polynomial time. As a by-product of our classification we obtain new families of exponential neighborhoods for the TSP which can be searched in polynomial time and for which conditions on the distance matrix can be formulated so that the search for an optimal TSP solution can be restricted to these exponential neighborhoods.
Original languageEnglish
Title of host publicationProceedings 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA, Miami FL, USA, January 22-24, 2006)
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)0-89871-605-5
Publication statusPublished - 2006


Dive into the research topics of 'Four point conditions and exponential neighborhoods for the symmetric TSP'. Together they form a unique fingerprint.

Cite this