Halin graphs and the travelling salesman problem

DOI10.1007/BF02591867zbMath0506.90083OpenAlexW2029841189MaRDI QIDQ4744083

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

Publication date: 1983

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

polynomial algorithmtravelling salesman problempolyhedral combinatoricsHalin graphedge cutsetinteger polytopehamilton cyclesroofless polyhedron

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)

Related Items (43)

Decomposition of 3-connected graphs ⋮ A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph ⋮ On Halin subgraphs and supergraphs ⋮ Steiner problem in Halin networks ⋮ Multiobjective traveling salesperson problem on Halin graphs ⋮ Extremal Halin graphs with respect to the signless Laplacian spectra ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ On two-connected subgraph polytopes ⋮ Hamiltonian properties of Toeplitz graphs ⋮ The book thickness of 1-planar graphs is constant ⋮ Optimally solving the joint order batching and picker routing problem ⋮ Forbidden pairs and the existence of a spanning Halin subgraph ⋮ Plane Triangulations Without a Spanning Halin Subgraph II ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ The Rique-number of graphs ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Treetopes and their graphs ⋮ A lower bound on the Hamiltonian path completion number of a line graph ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Symmetry breaking in planar and maximal outerplanar graphs ⋮ Dominating cycles in Halin graphs ⋮ On cycle cones and polyhedra ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ Traveling salesman problem under categorization ⋮ A survey of very large-scale neighborhood search techniques ⋮ One- and two-page crossing numbers for some types of graphs ⋮ The traveling salesman problem: new polynomial approximation algorithms and domination analysis ⋮ On dispersable book embeddings ⋮ Treelike snarks ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Normal 6-edge-colorings of some bridgeless cubic graphs ⋮ Boxicity of Halin graphs ⋮ Dirac's Condition for Spanning Halin Subgraphs ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Intersections and circuits in sets of line segments ⋮ On mixed linear layouts of series-parallel graphs ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ The traveling salesman problem on a graph and some related integer polyhedra ⋮ On Mixed Linear Layouts of Series-Parallel Graphs ⋮ Light on the infinite group relaxation. I: Foundations and taxonomy

Cites Work

• Unnamed Item
• Unnamed Item
• The traveling salesman problem in graphs with 3-edge cutsets
• Dual integrality in b-matching problems
• Minimum dominating cycles in outerplanar graphs
• Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings
• On a Family of Planar Bicritical Graphs

This page was built for publication: Halin graphs and the travelling salesman problem