On the Relation Between the Traveling-Salesman and the Longest-Path Problems

William W. Hardgrave and George L. Nemhauser
Additional contact information
William W. Hardgrave: Bell Telephone Laboratories, Inc., Holmdel, New Jersey
George L. Nemhauser: The Johns Hopkins University, Baltimore, Maryland

Operations Research, 1962, vol. 10, issue 5, 647-657

Abstract: The main result of this paper is that the traveling-salesman problem is a special case of the longest-path problem. Two formulations of the traveling-salesman problem are considered, the version in which the salesman visits each city exactly once and the more general formulation in which each city may be visited more than once. Both cases are reduced to the problem of finding the longest path between two nodes in a finite, connected graph. The remainder of the paper is then devoted to possible algorithms for the longest-path problem, since none presently exist.

Date: 1962
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.10.5.647 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:10:y:1962:i:5:p:647-657

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().