The traveling salesman problem in graphs with some excluded minors

DOI10.1007/BF01585700zbMath0780.05034MaRDI QIDQ1184343

Denis Naddef, Jean Fonlupt

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

characterization; convex hull; Eulerian graphs; traveling salesman problem; excluded minors; Hamilton cycle; walk; tour

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C38: Paths and cycles

05C45: Eulerian and Hamiltonian graphs

Related Items

Polyhedral study of the capacitated vehicle routing problem, On the graphical relaxation of the symmetric traveling salesman polytope, The box-TDI system associated with 2-edge connected spanning subgraphs, On the core of a traveling salesman cost allocation game, Two-edge connected spanning subgraphs and polyhedra, On the core of routing games, On perfectly two-edge connected graphs, The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points., Survey of facial results for the traveling salesman polytope, Traveling salesman path problems, \(k\)-edge connected polyhedra on series-parallel graphs, The 2-edge-connected subgraph polyhedron, Critical extreme points of the 2-edge connected spanning subgraph polytope, A note on the 5-person traveling salesman game, On the Steiner 2-edge connected subgraph polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• The traveling salesman problem in graphs with 3-edge cutsets
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Dynamic programming and the graphical traveling salesman problem
• Some Results Concerning the Structure of Graphs