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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: July 13, 2004.