An improved upper bound for the TSP in cubic 3-edge-connected graphs
From MaRDI portal
Publication:2488197
DOI10.1016/j.orl.2004.09.005zbMath1195.90091OpenAlexW1993298089MaRDI QIDQ2488197
David Gamarnik, Moshe Lewenstein, M. I. Sviridenko
Publication date: 25 August 2005
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2004.09.005
Related Items (15)
A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs ⋮ Multiobjective traveling salesperson problem on Halin graphs ⋮ Improved Approximations for Cubic Bipartite and Cubic TSP ⋮ Approximation hardness of graphic TSP on cubic graphs ⋮ On Dominating Even Subgraphs in Cubic Graphs ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ The traveling salesman problem on cubic and subcubic graphs ⋮ 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 ⋮ TSP on Cubic and Subcubic Graphs ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Improved approximations for cubic bipartite and cubic TSP ⋮ An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs ⋮ Approximating TSP walks in subcubic graphs
Cites Work
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- The traveling salesman problem and its variations
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Heuristic analysis, linear programming and branch and bound
- Approximation Algorithms for the Traveling Salesman Problem with Range Condition
- The Traveling Salesman Problem with Distances One and Two
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An improved upper bound for the TSP in cubic 3-edge-connected graphs
