The Traveling Salesman Problem in graphs with some excluded minors

The Traveling Salesman Problem in graphs with some excluded minors

0.00 Avg rating0 Votes
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: ,
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.