The traveling salesman problem in graphs with 3-edge cutsets

DOI10.1145/3149.3154zbMath0634.90089OpenAlexW1968919074WikidataQ128524564 ScholiaQ128524564MaRDI QIDQ3773723

Denis Naddef, Cornuéjols, Gérard, William R. Pulleyblank

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3149.3154

zbMATH Keywords

traveling salesman problempolynomial algorithmHalin graphsgraph decompositionspolynomial solutioninteger polytopesprismatic graphs3-edge cutsetdecomposition properties of a graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (19)

Decomposition and optimization over cycles in binary matroids ⋮ Complete linear descriptions of small asymmetric traveling salesman polytopes ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ Hamiltonian properties of Toeplitz graphs ⋮ Plane Triangulations Without a Spanning Halin Subgraph II ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Polyhedron of triangle-free simple 2-matchings in subcubic graphs ⋮ On cycle cones and polyhedra ⋮ The traveling salesman problem in graphs with some excluded minors ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ On cuts and matchings in planar graphs ⋮ Locating facilities which interact: Some solvable cases ⋮ Unnamed Item ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Subclasses of solvable problems from classes of combinatorial optimization problems ⋮ Halin graphs and the travelling salesman problem ⋮ The projected faces property and polyhedral relations

This page was built for publication: The traveling salesman problem in graphs with 3-edge cutsets