Finding 2-factors closer to TSP tours in cubic graphs

DOI10.1137/110843514MaRDI QIDQ2848544zbMATHOpenAlexFDO

Authors Sylvia Boyd, Satoru Iwata, Kenjiro Takazawa

Publication date 26 September 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/bf4ef55f60d35636ad6bbed7251e6640f1b2aca4

zbMATH Keywords

2-factor covering 3- and 4-edge cutsbridgeless cubic graphsminimum 2-edge-connected spanning subgraphsminimum-weight 2-factor covering 3-edge cutspolyhedral description of 2-factors covering 3-edge cuts

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• TSP tours in cubic graphs: beyond 4/3
• TSP tours in cubic graphs: beyond 4/3
• TSP on cubic and subcubic graphs
• Improved approximations for cubic bipartite and cubic TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Cubic TSP: A 1.3-Approximation
• An Improved Exact Algorithm for Cubic Graph TSP
• A new upper bound for the traveling salesman problem in cubic graphs
• The Traveling Salesman Problem for Cubic Graphs
• Approximation hardness of graphic TSP on cubic graphs

Cited in

(18)

• The parity Hamiltonian cycle problem in directed graphs
• Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
• Shorter tours and longer detours: uniform covers and a bit beyond
• The salesman's improved tours for fundamental classes
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• The parity Hamiltonian cycle problem
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• Packing $k$-Matchings and $k$-Critical Graphs
• Finding triangle-free 2-factors in general graphs
• Synchronized traveling salesman problem
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Fast algorithm to find 2-factor of minimum weight
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges

This page was built for publication: Finding 2-factors closer to TSP tours in cubic graphs

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