A 97-approximation algorithm for graphic TSP in cubic bipartite graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2014.284MaRDI QIDQ2969624zbMATH OpenOpenAlexFDO

Authors Jeremy A. Karp, R. Ravi

Publication date 22 March 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.284

zbMATH Keywords

approximation algorithmsBarnette's conjecturecombinatorial optimizationtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• Graphic TSP in cubic graphs
• Improved approximations for cubic bipartite and cubic TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Approximation hardness of graphic TSP on cubic graphs

Cited in

(5)

• Decomposition theorems for square-free 2-matchings in bipartite graphs
• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Approximation hardness of graphic TSP on cubic graphs
• Approximating the bipartite TSP and its biased generalization

This page was built for publication: A \(\frac {9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969624)