Lower and upper bounds for the degree-constrained minimum spanning tree problem

DOI10.1002/NET.20166MaRDI QIDQ3593370zbMATH OpenOpenAlexFDO

Authors Alexandre Salles da Cunha, Abilio Lucena

Publication date 20 July 2007

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20166

zbMATH Keywords

Lagrangian relaxationblossom inequalitiesdegree constrained minimum spanning treeLagrangian warm start to cutting plane algorithmsnon-delayed relax-and-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
• A parallel Lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• A branch and cut method for the degree-constrained minimum spanning tree problem

Cited in

(30)

• Exact algorithms for the vertex separator problem in graphs
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• A stronger lower bound on parametric minimum spanning trees
• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• The salesman and the tree: the importance of search in CP
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
• Binary Steiner trees: structural results and an exact solution approach
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• Spanning trees with variable degree bounds
• Further contributions to network optimization
• Relax-and-cut as a preprocessor and warm starter to branch-and-cut
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• Lagrangian heuristics for the quadratic knapsack problem
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
• A strong symmetric formulation for the min-degree constrained minimum spanning tree problem
• Degree-bounded minimum spanning tree for unit disk graph
• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
• A parallel Lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Spanning trees with node degree cependent costs and knapsack reformulations
• Design of capacitated degree constrained min-sum arborescence
• Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
• MaxMin allocation via degree lower-bounded arborescences

This page was built for publication: Lower and upper bounds for the degree-constrained minimum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3593370)