We consider traveling salesman problems (TSPs) 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(m3 + 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.
Burkard, R. E., Deineko, V. G., & Woeginger, G. J. (1998). The travelling salesman problem on permuted Monge matrices. Journal of Combinatorial Optimization, 2(4), 333-350. https://doi.org/10.1023/A:1009768317347