The travelling salesman and the PQ-tree

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

15 Citaten (Scopus)
2 Downloads (Pure)


Let D = (dij) be the n x n distance matrix of a set of n cities {1, 2, ..., n}, and let T be a PQ-tree with node degree bounded by d that represents a set (T) of permutations over {1, 2, ..., n}. We show how to compute for D in O(2dn3) time the shortest travelling salesman tour contained in (T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour. A consequence of our result is that the shortcutting phase of the "twice around the tree" heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.
Originele taal-2Engels
Pagina's (van-tot)613-623
TijdschriftMathematics of Operations Research
Nummer van het tijdschrift3
StatusGepubliceerd - 1998

Vingerafdruk Duik in de onderzoeksthema's van 'The travelling salesman and the PQ-tree'. Samen vormen ze een unieke vingerafdruk.

Citeer dit