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

DOI10.1016/j.dam.2011.08.008zbMath1321.05046MaRDI 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 optimization; branch-and-cut; integer programming formulations; min-degree constrained minimum spanning tree problem

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

90C10: Integer programming

90C27: Combinatorial optimization

Related Items

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, 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, The generalized dependency constrained spanning tree problem

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