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.

Abstract

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.


Actions:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/55