# zbMATH — the first resource for mathematics

Well-solved special cases. (English) Zbl 0631.90081
The traveling salesman problem, a guided tour of combinatorial optimization, 87-143 (1985).
[For the entire collection see Zbl 0562.00014.]
The authors give an excellent survey on special travelling salesman problems which can be solved by polynomial algorithms. There are two kinds of conditions possible: algebraic conditions for the cost matrix or graph theoretic conditions on the underlying network. In particular the following problem classes are treated: the “constant” TSP yields the same objective function value for all tours. Its cost elements have the form $$c_{ij}=ai+b_ j$$ for given vectors $$a=(a_ i)$$ and $$b=(b_ j)$$. Also “small TSP’s” with $$c_{ij}=\min \{a_ i,b_ j\}$$ can be solved polynomially, whereas Sarvanov showed that the TSP with product matrices $$c_{ij}=a_ ib_ j$$ is NP-hard. A proof of this famous theorem is given. Moreover, an extensive survey on the general Demidenko- conditions, the theory of pyramidal tours and subtour patching is given (inclusive proofs). Here also the Gilmore-Gomory case is treated.
Moreover it is mentioned that circulants as cost-matrices allow to find polynomially an open Hamiltonian path whereas it is an open question whether the Hamiltonian tour problem is NP-hard. TSPs with graded matrices $$(c_{ij}\leq c_{ij+1}$$ for all i,j) are NP-hard for sum objectives, but polynomially tractible for bottleneck objectives. TSPs with upper triangular cost-matrices can be solved via assignment problems. This leads to graphtheoretic conditions: TSPs on networks with limited bound widths and on Halin graphs can be solved by efficient algorithms.
Reviewer: R.E.Burkard

##### MSC:
 90C35 Programming involving graphs or networks 90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming 68Q25 Analysis of algorithms and problem complexity 05C35 Extremal problems in graph theory