A Lagrangean approach to the degree-constrained minimum spanning tree problem
type: Item
instance of: scholarly article
title: A Lagrangean approach to the degree-constrained minimum spanning tree problem
zbMATH Open document ID: 0674.90071
DOI: 10.1016/0377-2217(89)90169-0
author: A. Volgenant
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
review text: The author presents an improved branch and bound algorithm for large random table problems and related variations of the Minimum Spanning Tree (MST) problem. Lagrange multipiers are used for better edge elimination analysis. Computational results (for up to 150 nodes) illustrate the effectiveness of the Lagrangean approach for such problems.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4104719
zbMATH Keywords: degree-constrained trees
zbMATH Keywords: branch and bound
zbMATH Keywords: large random table problems
zbMATH Keywords: Minimum Spanning Tree
zbMATH Keywords: Lagrange multipiers
zbMATH Keywords: edge elimination
zbMATH Keywords: Computational results
MaRDI profile type: Publication
full work available at URL: 0377-2217(89)90169-0
OpenAlex ID: W1971782520
cites work: Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
cites work: Efficient algorithms for a family of matroid intersection problems
cites work: Q4198056
cites work: Topological design of centralized computer networks—formulations and algorithms
cites work: Q4178782
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Edge exchanges in the degree-constrained minimum spanning tree problem
cites work: The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
cites work: The Held—Karp algorithm and degree-constrained minimum 1-trees
description: scientific article; zbMATH DE number 4104719