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. 96-102.


Minimum weight 1-trees provide a well-known lower bound for the symmetric traveling salesman problem. We 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. We propose an O(m loglog n +|S|(n|S|+m alpha(m,n))) algorithm for this problem and report on its use in a Lagrangian approach to the traveling salesman problem.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr88-055
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 24 Oct 2011 14:36