The Traveling Salesman Problem on a Graph and Some Related Integer Polyhedra.
Abstract
Given a graph G = (N,E) and a certain length functions the Graphical Traveling Salesman Problem is that of finding a minimum length cycle going at least once through each node of G. This formulation has advantages over the traditional formulation where each node must be visited exactly once. The authors give some facet inducing inequalities of the convex hull of the solutions to that problem. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given when G is a series-parallel graph.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1984
- Accession Number
- ADA147953
Entities
People
- D. Naddef
- G. Cornuejols
- J. Fonlupt
Organizations
- Carnegie Mellon University