The symmetric travelling salesman problem II. New low bounds
S. I. Sergeev · Automation and Remote Control · 2010
The branch-and-bound method is adduced for the symmetric salesman problem where two lower bounds are proposed as bounds. The first bound is a solution to the problem of optimal 2-matching; the second one, to the problem of minimum spanning 1-tree. The last bound is enhanced by applying the problem of optimal 2-matching. Both these bounds considerably improve the symmetric traveling salesman problem as compared to the asymmetric problem.