TSP Tours in Cubic Graphs: Beyond 4/3
From MaRDI portal
Publication:5254089
DOI10.1137/140972925zbMath1314.05199OpenAlexW2138233424WikidataQ65553899 ScholiaQ65553899MaRDI QIDQ5254089
Omar Larré, José R. Correa, Jose A. Soto
Publication date: 8 June 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10533/148030
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)
Related Items (14)
A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs ⋮ A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs ⋮ Improved Approximations for Cubic Bipartite and Cubic TSP ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ Cubic TSP: A 1.3-Approximation ⋮ On Dominating Even Subgraphs in Cubic Graphs ⋮ Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals ⋮ Special Frequency Quadrilaterals and an Application ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ Simple cubic graphs with no short traveling salesman tour ⋮ Improved approximations for cubic bipartite and cubic TSP ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ Approximating TSP walks in subcubic graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- Worst-case comparison of valid inequalities for the TSP
- Worst-case analysis of a new heuristic for the travelling salesman problem
- On the integrality gap of the subtour LP for the 1,2-TSP
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- On the approximability of the traveling salesman problem
- TSP on Cubic and Subcubic Graphs
- A new proof of 3-colorability of Eulerian triangulations
- Improved Inapproximability for TSP
- Approximation hardness of graphic TSP on cubic graphs
- Heuristic analysis, linear programming and branch and bound
- Fractional Packing ofT-Joins
- Eight-Fifth Approximation for the Path TSP
- Improving christofides' algorithm for the s-t path TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- On Hamiltonian Circuits
This page was built for publication: TSP Tours in Cubic Graphs: Beyond 4/3
