Efficiently solvable special case of bottleneck travelling salesman problems

The paper investigates bottleneck travelling salesman problems (BTSP) which can be solved in polynomial time. At first a BTSP whose cost matrix is a circulant is treated. It is shown that in the symmetric case such a BTSP can be solved in O(nlogn) time. Secondly conditions are derived which guarantee that an optimal solution is a pyramidal tour. Thus this problem can be solved in O(n²) time. Finally it is shown that a BTSP with cost matrix C=(cij), where cij=aibj with a1•ëëë•an and b1≥ëëë≥bn can be solved in O(n²) time.