Finding 2-Factors Closer to TSP Tours in Cubic Graphs

DOI10.1137/110843514zbMath1272.05190OpenAlexW2048952924MaRDI QIDQ2848544

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

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

Related Items (16)

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

This page was built for publication: Finding 2-Factors Closer to TSP Tours in Cubic Graphs