The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
From MaRDI portal
Publication:496663
DOI10.1016/j.dam.2011.08.008zbMath1321.05046OpenAlexW1981354702MaRDI QIDQ496663
Leonardo Conegundes Martinez, Alexandre Salles da Cunha
Publication date: 22 September 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.08.008
combinatorial optimizationbranch-and-cutinteger programming formulationsmin-degree constrained minimum spanning tree problem
Trees (05C05) Extremal problems in graph theory (05C35) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items (8)
The generalized dependency constrained spanning tree problem ⋮ A strong symmetric formulation for the min-degree constrained minimum spanning tree problem ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ A unifying model for locally constrained spanning tree problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman 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
- VNS and second order heuristics for the min-degree constrained minimum spanning tree problem
- Edge exchanges in the degree-constrained minimum spanning tree problem
- A Lagrangean approach to the degree-constrained minimum spanning tree problem
- Variable neighborhood search for the degree-constrained minimum spanning tree problem
- Variable neighborhood search
- Strong lower bounds for the prize collecting Steiner problem in graphs
- Lagrangean relaxation. (With comments and rejoinder).
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- The multi-weighted Steiner tree problem: A reformulation by intersection
- Using Lagrangian dual information to generate degree constrained spanning trees
- A branch and cut method for the degree-constrained minimum spanning tree problem
- md-MST is NP-hard for
- Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- Reformulation by Intersection Method on the MST Problem with Lower Bound on the Number of Leaves
- Integer Programming Formulation of Traveling Salesman Problems
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Lower and upper bounds for the degree-constrained minimum spanning tree problem
- Trees and Cuts
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Topological design of centralized computer networks—formulations and algorithms
- Solving Steiner tree problems in graphs to optimality
This page was built for publication: The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
