The traveling salesman problem in graphs with some excluded minors

DOI10.1007/BF01585700zbMath0780.05034OpenAlexW1981894795MaRDI QIDQ1184343

Jean Fonlupt, Denis Naddef

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1007/bf01585700

zbMATH Keywords

characterizationconvex hullEulerian graphstraveling salesman problemexcluded minorsHamilton cyclewalktour

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (24)

Two-edge connected spanning subgraphs and polyhedra ⋮ Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron ⋮ On the core of routing games ⋮ On perfectly two-edge connected graphs ⋮ On the core of a traveling salesman cost allocation game ⋮ On the graphical relaxation of the symmetric traveling salesman polytope ⋮ Optimally solving the joint order batching and picker routing problem ⋮ The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points. ⋮ On the Circuit Diameter of Some Combinatorial Polytopes ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ Traveling salesman path problems ⋮ Polyhedral study of the capacitated vehicle routing problem ⋮ On the Steiner 2-edge connected subgraph polytope ⋮ A branch-and-cut algorithm for the k-edge connected subgraph problem ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ The box-TDI system associated with 2-edge connected spanning subgraphs ⋮ Packing circuits in matroids ⋮ Cut Dominants and Forbidden Minors ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ On the facial structure of symmetric and graphical traveling salesman polyhedra ⋮ The 2-edge-connected subgraph polyhedron ⋮ Survey of facial results for the traveling salesman polytope ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ A note on the 5-person traveling salesman game

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

This page was built for publication: The traveling salesman problem in graphs with some excluded minors