# zbMATH — the first resource for mathematics

The travelling salesman problem on permuted Monge matrices. (English) Zbl 0955.90113
Summary: We consider traveling salesman problems with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov’s theory. These results are then used for designing an $$O(m^3+ mn)$$ algorithm in the case of multitrees, where $$n$$ is the number of cities and $$m$$ is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.

##### MSC:
 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems
Full Text: