A 4/3-approximation for TSP on cubic 3-edge-connected graphs
From MaRDI portal
Publication:2417175
DOI10.1016/j.orl.2018.04.007OpenAlexW2963104161MaRDI QIDQ2417175
Nishita Agarwal, Naveen Garg, Swati Gupta
Publication date: 11 June 2019
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.5586
Related Items (1)
Cites Work
- A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite 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
- \(\frac{13}{9}\)-approximation for graphic TSP
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- TSP on Cubic and Subcubic Graphs
- Improved Approximations for Cubic Bipartite and Cubic TSP
- Spanning even subgraphs of 3‐edge‐connected graphs
- A Reduction Method for Edge-Connectivity in Graphs
- Faster scaling algorithms for general graph matching problems
- Approximating Graphic TSP by Matchings
- The traveling-salesman problem and minimum spanning trees: Part II
This page was built for publication: A 4/3-approximation for TSP on cubic 3-edge-connected graphs
