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

DOI10.1016/0377-2217(89)90169-0zbMath0674.90071OpenAlexW1971782520MaRDI QIDQ1121788

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 resultsedge eliminationdegree-constrained treesLagrange multipierslarge random table problemsMinimum Spanning Tree

Mathematics Subject Classification ID

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

Related Items

Variable neighborhood search for the degree-constrained minimum spanning tree problem, Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations, The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems, Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm, A hop constrained min-sum arborescence with outage costs, Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs., Degree-constrained \(k\)-minimum spanning tree problem, A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees, The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm, Branch and cut methods for network optimization, Using Lagrangian dual information to generate degree constrained spanning trees, DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH, Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints, 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, Design of capacitated degree constrained min-sum arborescence, A multiperiod degree constrained minimal spanning tree problem, Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Efficient algorithms for a family of matroid intersection problems
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• Topological design of centralized computer networks—formulations and algorithms
• The Held—Karp algorithm and degree-constrained minimum 1-trees
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II