The traveling salesman problem in graphs with some excluded minors (Q1184343): Difference between revisions
From MaRDI portal
Revision as of 15:04, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The traveling salesman problem in graphs with some excluded minors |
scientific article |
Statements
The traveling salesman problem in graphs with some excluded minors (English)
0 references
28 June 1992
0 references
Let \(G=(V,E)\) be a finite, loopless, undirected graph with vertex set \(V\) and edge set \(E\) having non-negative edge weights. A tour \(T\) of \(G\) is a closed walk that passes through each vertex of \(G\). The length of \(T\) is the sum of the lengths of the edges in \(T\). The Graphical Traveling Salesman Problem is that of finding a tour in \(G\) of minimum length. The authors characterize those graphs for which the convex hull of all solutions is given by the non-negativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given.
0 references
traveling salesman problem
0 references
Eulerian graphs
0 references
Hamilton cycle
0 references
tour
0 references
walk
0 references
convex hull
0 references
characterization
0 references
excluded minors
0 references