Cubic TSP: A 1.3-Approximation

DOI10.1137/15M1032247zbMath1393.05165arXiv1506.06369OpenAlexW2964107041MaRDI QIDQ4581212

Barbora Duník, Robert Lukot'ka

Publication date: 15 August 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.06369

zbMATH Keywords

traveling salesman problemcubic graphsgraphic TSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38)

Related Items (1)

2-factors of cubic bipartite graphs

Cites Work

• Avoiding 7-circuits in 2-factors of cubic graphs
• The traveling salesman problem on cubic and subcubic graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Improved Inapproximability for TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP
• 8/7-approximation algorithm for (1,2)-TSP
• Graphic TSP in cubic graphs
• Fractional Packing ofT-Joins
• TSP Tours in Cubic Graphs: Beyond 4/3
• Approximating Graphic TSP by Matchings
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Cubic TSP: A 1.3-Approximation