The travelling salesman and the PQ-tree (vol 23, pg 613, 1998)
成果类型：
Correction
署名作者：
Burkard, RE; Deineko, VG; Woeginger, GJ
署名单位：
Graz University of Technology; University of Warwick
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.24.1.262
发表日期：
1999
页码：
262-272
关键词：
摘要：
Let D = (d(ij)) be the n x n distance matrix of a set of a cities {1, 2, ..., n}, and let Tbe a PQ-tree with node degree bounded by d that represents a set II(T) of permutations over {1, 2, ..., n}. We show how to compute for a in O(2(d)n(3)) time the shortest travelling salesman tour contained in IT(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.