Halin graphs and the travelling salesman problem

DOI10.1007/BF02591867MaRDI QIDQ4744083zbMATH OpenOpenAlexFDO

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

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

polyhedral combinatoricspolynomial algorithmHalin graphtravelling salesman problemedge 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)

Cites work

• scientific article; zbMATH DE number 3609444 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Dual integrality in b-matching problems
• Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings
• Minimum dominating cycles in outerplanar graphs
• On a Family of Planar Bicritical Graphs
• The traveling salesman problem in graphs with 3-edge cutsets

Cited in

(40)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4744083)