In this paper we consider a combinatorial optimization problem that is similar to the bottleneck traveling salesman problem. We show that an optimal tour for this problem is pyramidal tour (1, 3, 5, , n, , 6, 4, 2) or consists of some pyramidal subtours. The above 7methods can be extended to complete bipartite graphs. 1. Problem statement It is well-known that the traveling salesman problem (TSP) is strongly NP-hard (cf. [1], p. 353). But for some special cases of the TSP can be solvable in polynomial time. .
