Cubic TSP - a 1.3-approximation
arXiv:1506.06369
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.
21 pages
arXiv:1506.06369
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.
21 pages