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.

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