Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations

DOI10.1016/j.cor.2017.03.001zbMath1391.90602OpenAlexW2592716126MaRDI QIDQ1652314

Fabio C. S. Dias, Rafael Andrade, Críston Souza, Manoel B. Campêlo

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.03.001

zbMATH Keywords

integer programmingLagrangian heuristicmin-degree constrained minimum spanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (4)

The generalized dependency constrained spanning tree problem ⋮ Improved approaches to solve the one-to-one skewgram problem ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ A unifying model for locally constrained spanning tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• 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
• Using separation algorithms to generate mixed integer model reformulations
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Using Lagrangian dual information to generate degree constrained spanning trees
• A branch and cut method for the degree-constrained minimum spanning tree problem
• 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
• A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem
• Integer Programming Formulation of Traveling Salesman Problems
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Trees and Cuts
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Convergence Analysis of Deflected Conditional Approximate Subgradient Methods
• Solution of a Large-Scale Traveling-Salesman Problem
• On a graph theorem by dirac

This page was built for publication: Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations