Improved Approximations for Cubic Bipartite and Cubic TSP

DOI10.1007/978-3-319-33461-5_21zbMath1419.90100OpenAlexW2467906027MaRDI QIDQ3186507

Anke van Zuylen

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-33461-5_21

zbMATH Keywords

approximation algorithmtraveling salesman problemcubic graphsBarnette's conjecturecubic bipartite graphs

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs ⋮ A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs ⋮ Improved Approximations for Cubic Bipartite and Cubic TSP ⋮ Cubic TSP: A 1.3-Approximation ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ Simple cubic graphs with no short traveling salesman tour ⋮ Approximating TSP walks in subcubic graphs

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
• \(\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 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
• Improved Approximations for Cubic Bipartite and Cubic TSP
• TSP Tours in Cubic Graphs: Beyond 4/3
• Approximating Graphic TSP by Matchings
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: Improved Approximations for Cubic Bipartite and Cubic TSP