Halin graphs and the travelling salesman problem

polyhedral combinatorics polynomial algorithm Halin graph travelling salesman problem edge cutset integer polytope hamilton cycles roofless 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

The traveling salesman problem in graphs with 3-edge cutsets
Title not available (Why is that?)
Ear Decompositions of Elementary Graphs and GF2-rank of Perfect Matchings
Minimum dominating cycles in outerplanar graphs
Title not available (Why is that?)
Dual integrality in b-matching problems
On a Family of Planar Bicritical Graphs

Cited In (40)

Traveling salesman problem under categorization
Fast local search algorithms for the handicapped persons transportation problem
Boxicity of Halin graphs
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
One- and two-page crossing numbers for some types of graphs
A survey of very large-scale neighborhood search techniques
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
Dirac's condition for spanning Halin subgraphs
Optimally solving the joint order batching and picker routing problem
Normal 6-edge-colorings of some bridgeless cubic graphs
The Rique-number of graphs
On two-connected subgraph polytopes
Hamiltonian properties of Toeplitz graphs
Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
The traveling salesman problem: new polynomial approximation algorithms and domination analysis
Multiobjective traveling salesperson problem on Halin graphs
Steiner problem in Halin networks
A lower bound on the Hamiltonian path completion number of a line graph
Intersections and circuits in sets of line segments
Efficiently solvable special cases of hard combinatorial optimization problems
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
On cycle cones and polyhedra
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

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)