A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
From MaRDI portal
Publication:298977
DOI10.1016/j.dam.2015.10.038zbMath1339.05389arXiv1311.3640OpenAlexW2964056290MaRDI QIDQ298977
Publication date: 21 June 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.3640
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (4)
Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ Improved approximations for cubic bipartite and cubic TSP
Cites Work
- 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
- The traveling salesman problem on cubic and subcubic graphs
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs
- Improved Approximations for Cubic Bipartite and Cubic TSP
- TSP Tours in Cubic Graphs: Beyond 4/3
- Solution of a Large-Scale Traveling-Salesman Problem
- Short Tours through Large Linear Forests
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
