A Lagrangean approach to the degree-constrained minimum spanning tree problem

DOI10.1016/0377-2217(89)90169-0MaRDI QIDQ1121788zbMATH OpenOpenAlexFDO

Authors A. Volgenant

Publication date 1989

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(89)90169-0

zbMATH Keywords

branch and boundComputational resultsdegree-constrained treesedge eliminationLagrange multipierslarge random table problemsMinimum Spanning Tree

Mathematics Subject Classification ID

Trees (05C05) Numerical mathematical programming methods (65K05) Integer programming (90C10) Programming involving graphs or networks (90C35)

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.

Recommendations

• A branch and cut method for the degree-constrained minimum spanning tree problem
• A parallel Lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Using Lagrangian dual information to generate degree constrained spanning trees
• A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees

Cites work

• Edge exchanges in the degree-constrained minimum spanning tree problem
• Efficient algorithms for a family of matroid intersection problems
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The Held—Karp algorithm and degree-constrained minimum 1-trees
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Topological design of centralized computer networks—formulations and algorithms

Cited in

(24)

• VNS and second order heuristics for the min-degree constrained minimum spanning tree problem
• Minimal spanning trees with a constraint on the number of leaves
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs.
• Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm
• A multiperiod degree constrained minimal spanning tree problem
• Design of capacitated degree constrained min-sum arborescence
• Degree-constrained \(k\)-minimum spanning tree problem
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• Using Lagrangian dual information to generate degree constrained spanning trees
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• A parallel Lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem
• A strong symmetric formulation for the min-degree constrained minimum spanning tree problem
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• Branch and cut methods for network optimization
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• The tree labeling polytope: a unified approach to ancestral reconstruction problems
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• A hop constrained min-sum arborescence with outage costs

This page was built for publication: A Lagrangean approach to the degree-constrained minimum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121788)