Constrained Spanning Trees and the Travelling Salesman Problem
Leclerc, Matthias and Rendl, Franz
(1989)
Constrained Spanning Trees and the Travelling Salesman Problem.
Published in:
European journal of operational research Vol. 39 (1).
pp. 96102.
Abstract
Minimum weight 1trees provide a wellknown lower bound for the symmetric traveling salesman problem. We propose to strengthen this bound by imposing degreeconstraints upon the 1trees. The vertices for the constraints are chosen to form a stable set S. We propose an O(m loglog n +S(nS+m alpha(m,n))) algorithm for this problem and report on its use in a Lagrangian approach to the traveling salesman problem.
Actions:
Content information:
Item Type:  Article 

Citations:  No citation data. 
Uncontrolled Keywords:  1trees degreeconstraints lower bounds subgradient optimization 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
Deposit Information:
ZAIK Number:  zpr88055 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  24 Oct 2011 14:36 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/55 