Article ID: | iaor1993385 |
Country: | Netherlands |
Volume: | 53 |
Issue: | 2 |
Start Page Number: | 147 |
End Page Number: | 172 |
Publication Date: | Jan 1992 |
Journal: | Mathematical Programming (Series A) |
Authors: | Naddef Denis, Fonlupt Jean |
Keywords: | graphs |
Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper the authors characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs.