Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations

DOI10.1111/j.1475-3995.2011.00830.xzbMath1251.90347OpenAlexW2021438403MaRDI QIDQ2914198

Mauricio C. de Souza, Pedro Martins, Ana de Almeida

Publication date: 25 September 2012

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2011.00830.x

zbMATH Keywords

degree constrained spanning tree problemsmulticommodity flow formulationssingle-commodity flow formulations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (13)

md-MST is NP-hard for ⋮ Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm ⋮ The generalized dependency constrained spanning tree problem ⋮ Spanning trees with variable degree bounds ⋮ 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 ⋮ Lower and upper bounds for the spanning tree with minimum branch vertices ⋮ Two dependency constrained spanning tree problems ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ A unifying model for locally constrained spanning tree problems ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• Unnamed Item
• Prize collecting Steiner trees with node degree dependent costs
• 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
• Transitions in geometric minimum spanning trees
• Minimal spanning trees with a constraint on the number of leaves
• A greedy heuristic for a minimum-weight forest problem
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• An augmented arborescence formulation for the two-level network design problem
• Low-degree minimum spanning trees
• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs
• Using Lagrangian dual information to generate degree constrained spanning trees
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• On two geometric problems related to the travelling salesman problem
• Topological design of centralized computer networks—formulations and algorithms
• Comparison of algorithms for the degree constrained minimum spanning tree

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