Edge exchanges in the degree-constrained minimum spanning tree problem

DOI10.1016/0305-0548(85)90032-2zbMath0608.90098OpenAlexW2033983963MaRDI QIDQ1086497

Ton Volgenant, Savelsbergh, Martin W. P.

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

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

Related Items

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

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Edge exchanges in the degree-constrained minimum spanning tree problem
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Topological design of centralized computer networks—formulations and algorithms
• The traveling-salesman problem and minimum spanning trees: Part II