The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm

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

zbMATH Keywords

combinatorial optimizationbranch-and-cutinteger programming formulationsmin-degree constrained minimum spanning tree problem

Mathematics Subject Classification ID

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

• SteinLib
• CPLEX

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