The traveling salesman problem in graphs with some excluded minors |
| |
Authors: | Jean Fonlupt Denis Naddef |
| |
Institution: | (1) Université J. Fourier, IMAG-Artemis, 38041 Grenoble, France |
| |
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 we 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. |
| |
Keywords: | Graph Eulerian graph Hamilton cycle polyhedron Traveling Salesman Problem |
本文献已被 SpringerLink 等数据库收录! |