UNSPECIFIED (1998) The travelling salesman and the PQ-tree. MATHEMATICS OF OPERATIONS RESEARCH, 23 (3). pp. 613-623. ISSN 0364-765X

Full text not available from this repository.

Abstract

Let D = (d(ij)) 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 n(T) of permutations over {1, 2,..., n }. We show how to compute for D in O(2(d)n(3)) time the shortest travelling salesman tour contained in n(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 Article
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
Date:	August 1998
Volume:	23
Number:	3
Number of Pages:	11
Page Range:	pp. 613-623
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/14887

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item