Gilmore-Gomory type traveling salesman problems

One of the well-known, solvable cases of the traveling salesman problem (TS P) is the Gilmore-Gomory case. A generalization of their algorithm to what we call the GG scheme is known to solve a fairly large subclass of the prob lem, In this paper, we identify new classes of TSP for which the GG scheme produces an optimal solution and which properly include the class of TSP fo r which the cost matrix is a permuted distribution matrix. Implementation o f the GG scheme is NP-hard for these Classes of TSP, However. we identify s ome subclasses for which the GG scheme can be implemented in polynomial tim e, Some of these new solvable cases are proper generalizations of some well -known cases. (C) 1999 Elsevier Science Ltd. All rights reserved.