Constrained spanning trees and the traveling salesman problem
type: Item
instance of: scholarly article
title: Constrained spanning trees and the traveling salesman problem
zbMATH Open document ID: 0679.90085
DOI: 10.1016/0377-2217(89)90356-1
author: Matthias Leclerc
author: Franz Rendl
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
review text: Since the travelling salesman problem is very difficult to solve, it is of importance to find a good lower bound for the optimal value. A common method to bound the optimal value makes use of 1-trees. In this paper the authors strengthen this bound by imposing degree-constraints upon the 1- trees. This is achieved by choosing vertices for the constraints from a stable set containing 1. Computation of bounds is done using subgradient optimization. Computational results are presented.
reviewed by: Riho Lepp
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4114418
zbMATH Keywords: lower bound
zbMATH Keywords: 1-trees
zbMATH Keywords: degree-constraints
zbMATH Keywords: subgradient optimization
MaRDI profile type: Publication
full work available at URL: 0377-2217(89)90356-1
OpenAlex ID: W2045983984
cites work: Q3686500
cites work: Cliques in random graphs
cites work: A Method for Solving Traveling-Salesman Problems
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: Q3786484
cites work: Q5187226
cites work: Q4739657
cites work: A multiply constrained matroid optimization problem
cites work: Q5187067
cites work: An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
description: scientific article; zbMATH DE number 4114418