### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 333-350 |

Number of pages | 18 |

Journal | Journal of Combinatorial Optimization |

Volume | 2 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1998 |

## Fingerprint Dive into the research topics of 'The travelling salesman problem on permuted Monge matrices'. Together they form a unique fingerprint.

## Cite this

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