A 4/3-approximation for TSP on cubic 3-edge-connected graphs

Abstract

We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.

Cited by in corpus (2)

• The traveling salesman problem on cubic and subcubic graphs
• Graph-TSP from Steiner Cycles