The Library
The travelling salesman and the PQ-tree (vol 23, pg 613, 1998)
Tools
UNSPECIFIED (1999) The travelling salesman and the PQ-tree (vol 23, pg 613, 1998). MATHEMATICS OF OPERATIONS RESEARCH, 24 (1). pp. 262-272.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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.
Item Type: | Journal Item | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management Q Science > QA Mathematics |
||||
Journal or Publication Title: | MATHEMATICS OF OPERATIONS RESEARCH | ||||
Publisher: | INST OPERATIONS RESEARCH MANAGEMENT SCIENCES | ||||
ISSN: | 0364-765X | ||||
Official Date: | February 1999 | ||||
Dates: |
|
||||
Volume: | 24 | ||||
Number: | 1 | ||||
Number of Pages: | 11 | ||||
Page Range: | pp. 262-272 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |