## 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).
*
### Abstract

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.