Long-Chord-Free and Fence-Free Tours for the Travelling Salesman Problem

摘要

The authors introduce the concept of long-chord-free and fence-free tours inconnection with the traveling salesman problem (TSP). These tours form a non-trivial subset of the cycle permutations. The authors prove that the shortest long-chord-free and fence-free TSP tour can be computed in polynomial time by a dynamic programming approach. As an application, the authors get that the Convex-hull-and-k-line TSP can be solved in polynomial time.