Finding 2-factors closer to TSP tours in cubic graphs

DOI10.1137/110843514zbMATH Open1272.05190OpenAlexW2048952924MaRDI QIDQ2848544FDOQ2848544

Sylvia Boyd, Kenjiro Takazawa, Satoru Iwata

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)

Cited In (17)

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

Recommendations

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

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)