Edge exchanges in the degree-constrained minimum spanning tree problem

DOI10.1016/0305-0548(85)90032-2MaRDI QIDQ1086497zbMATH OpenOpenAlexFDO

Authors Ton Volgenant, Martin W. P. Savelsbergh

Publication date 1985

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(85)90032-2

zbMATH Keywords

branch and boundComputational resultsdegree-constrained minimum spanning tree problemedge exchange analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Recommendations

• Degree-constrained \(k\)-minimum spanning tree problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• A multiperiod degree constrained minimal spanning tree problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• The most vital edges in the minimum spanning tree problem
• Approximating minimum-cost graph problems with spanning tree edges
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• The constrained minimum spanning tree problem

Cites work

• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• A note on two problems in connexion with graphs
• Edge exchanges in the degree-constrained minimum spanning tree problem
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Topological design of centralized computer networks—formulations and algorithms

Cited in

(23)

• A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs.
• Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
• Heuristic methods and applications: A categorized survey
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• A multiperiod degree constrained minimal spanning tree problem
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Network design for time‐constrained delivery
• Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm
• Using Lagrangian dual information to generate degree constrained spanning trees
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Branch and cut methods for network optimization
• Non delayed relax-and-cut algorithms
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Design of capacitated degree constrained min-sum arborescence
• An exact algorithm for multi-constrained minimum spanning tree problem

This page was built for publication: Edge exchanges in 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 Q1086497)