Constrained spanning trees and the traveling salesman problem

Minimum weight 1-trees provide a well-known lower bound for the symmetric traveling salesman problem. The authors propose to strengthen this bound by imposing degree-constraints upon the 1-trees. The vertices for the constraints are chosen to form a stable set S. The authors propose an O(mloglogn+ℝSℝ(nℝSℝ+mα(m,n))) algorithm for this problem and report on its use in a Lagrangian approach to the traveling salesman problem.