Vladimir G. Deineko, René van Dal, and Günter Rote:
The convex-hull-and-line traveling salesman problem: A solvable case
Information Processing Letters 51 (1994), 141-148, (Zbl 806.90121).
We solve the special case of the Euclidean Traveling Salesman Problem
where n-m cities lie on the boundary of the convex hull of all n
cities, and the other m cities lie on a line segment inside this
convex hull by an algorithm which needs O(mn) time and O(n) space.
This generalizes and improves previous results of Cutler (1980) for the
3-line Traveling Salesman Problem.
Last update: July 13, 2004.