Approximating TSP walks in subcubic graphs
From MaRDI portal
Publication:2101165
DOI10.1016/j.jctb.2022.09.002OpenAlexW4226436028MaRDI QIDQ2101165
Xingxing Yu, Youngho Yoo, Michael C. Wigal
Publication date: 28 November 2022
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2112.06278
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- 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
- New inapproximability bounds for TSP
- Worst-case comparison of valid inequalities for the TSP
- \(\frac{13}{9}\)-approximation for graphic TSP
- The traveling salesman problem on cubic and subcubic graphs
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Improved Inapproximability for TSP
- Finding the Exact Integrality Gap for Small Traveling Salesman Problems
- Improved Approximations for Cubic Bipartite and Cubic TSP
- Approximation hardness of graphic TSP on cubic graphs
- Graphic TSP in cubic graphs
- Reducibility among Combinatorial Problems
- TSP Tours in Cubic Graphs: Beyond 4/3
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- A (slightly) improved approximation algorithm for metric TSP
This page was built for publication: Approximating TSP walks in subcubic graphs
