Approximating TSP walks in subcubic graphs

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsgraphic TSP

Mathematics Subject Classification ID

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