A generalization of the convex-hull-and-line traveling salesman problem. Issue 2 (1998) - Baki, Md. Fazle; Kabadi, S. N.
Abstract : Two instances of the traveling salesman problem, on the same node set{ 1, 2, …, n } but with different cost matricesC andC ′, are equivalent iff there exist{ a i, b i :   i = 1, …,   n } such that for any1 ≤ i, j ≤ n, i ≠ j, C ′ ( i, j ) = C ( i, j ) + a i + b j [7]. One of the well-solved special cases of the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solution scheme for this class of TSP given in [9] to a more general class which is closed with respect to the above equivalence relation. The cost matrix in our general class is a certain composition of Kalmanson matrices. This gives a new, non-trivial solvable case of TSP.