Article ID: | iaor19931197 |
Country: | Netherlands |
Volume: | 12 |
Issue: | 2 |
Start Page Number: | 89 |
End Page Number: | 95 |
Publication Date: | Aug 1992 |
Journal: | Operations Research Letters |
Authors: | Punnen Abraham P. |
The paper introduces two new classes of traveling salesman problems (TSP1 and TSP2) which subsume the classical traveling salesman problem and the bottleneck traveling salesman problem. It is shown that these problems are strongly NP-complete on Halin graphs even though their extreme cases (i.e. traveling salesman problem and bottleneck traveling salesman problem) are solvable in polynomial time on such graphs. It is also shown that TSP2 is solvable in polynomial time on Halin graphs if an associated parameter