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

DOI10.1002/NET.20166zbMATH Open1119.90069OpenAlexW4251562717MaRDI QIDQ3593370FDOQ3593370

Abilio Lucena, Alexandre Salles da Cunha

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (28)

• 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
• Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
• On generalizations of network design problems with degree bounds
• Binary Steiner trees: structural results and an exact solution approach
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• Spanning trees with variable degree bounds
• Further contributions to network optimization
• Lagrangian heuristics for the quadratic knapsack problem
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• A strong symmetric formulation for the min-degree constrained minimum spanning tree problem
• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• Degree-bounded minimum spanning tree for unit disk graph
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• 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
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Spanning trees with node degree cependent costs and knapsack reformulations
• Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
• Design of capacitated degree constrained min-sum arborescence
• MaxMin allocation via degree lower-bounded arborescences

   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 👍 👎

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)