### Abstract

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.

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

Pages (from-to) | 613-623 |

Journal | Mathematics of Operations Research |

Volume | 23 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1998 |

## Fingerprint Dive into the research topics of 'The travelling salesman and the PQ-tree'. Together they form a unique fingerprint.

## Cite this

Burkard, R. E., Deineko, V. G., & Woeginger, G. J. (1998). The travelling salesman and the PQ-tree.

*Mathematics of Operations Research*,*23*(3), 613-623. https://doi.org/10.1287/moor.23.3.613