Cubic TSP - a 1.3-approximation

Barbora Candr\'akov\'a; Robert Luko\v{t}ka

arxiv: 1506.06369 · v2 · pith:JR4L2TCOnew · submitted 2015-06-21 · 💻 cs.DM · math.OC

Cubic TSP - a 1.3-approximation

Barbora Candr\'akov\'a , Robert Luko\v{t}ka This is my paper

classification 💻 cs.DM math.OC

keywords cubicapproximationbridgelessconstructedeverygraphlengthpolynomial

0 comments

read the original abstract

We prove that every simple bridgeless cubic graph with n >= 8 vertices has a travelling salesman tour of length at most 1.3n - 2, which can be constructed in polynomial time.

This paper has not been read by Pith yet.

Cubic TSP - a 1.3-approximation

discussion (0)