A branch and cut method for the degree-constrained minimum spanning tree problem
From MaRDI portal
Publication:2714906
DOI<74::AID-NET2>3.0.CO;2-E 10.1002/1097-0037(200103)37:2<74::AID-NET2>3.0.CO;2-EzbMath0967.90094OpenAlexW1996106387MaRDI QIDQ2714906
Louis Caccetta, Stephen P. Hill
Publication date: 20 June 2001
Full work available at URL: https://doi.org/10.1002/1097-0037(200103)37:2<74::aid-net2>3.0.co;2-e
Extremal problems in graph theory (05C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)
Related Items (16)
Spanning trees with variable degree bounds ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm ⋮ Degree-constrained \(k\)-minimum spanning tree problem ⋮ Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ A computational study on the maximum-weight bounded-degree rooted tree problem ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ 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 ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ Non delayed relax-and-cut algorithms ⋮ Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
Uses Software
This page was built for publication: A branch and cut method for the degree-constrained minimum spanning tree problem
