The travelling salesman problem on permuted Monge matrices

R.E. Burkard, V.G. Deineko, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Citations (Scopus)


    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 languageEnglish
    Pages (from-to)333-350
    Number of pages18
    JournalJournal of Combinatorial Optimization
    Issue number4
    Publication statusPublished - 1998


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

    Cite this