Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem

DOI10.1007/S10589-015-9788-7zbMATH Open1343.90101OpenAlexW1747465883MaRDI QIDQ263164FDOQ263164

Abilio Lucena, Luis Henrique Bicalho, Alexandre Salles da Cunha

Publication date: 4 April 2016

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-015-9788-7

Recommendations

• A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• Comparison of algorithms for the degree constrained minimum spanning tree

zbMATH Keywords

branch-and-cutbranch-and-cut-and-pricedegree constrained spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Cites Work

• Solving Steiner tree problems in graphs to optimality
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Benchmarking optimization software with performance profiles.
• Title not available (Why is that?)
• Solution of a Large-Scale Traveling-Salesman Problem
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Local branching
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Branching rules revisited
• Using Lagrangian dual information to generate degree constrained spanning trees
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Title not available (Why is that?)
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Trees and Cuts
• Topological design of centralized computer networks—formulations and algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on genetic algorithms for degree-constrained spanning tree problems
• Spanning tree manipulation and the travelling salesman problem
• Integer Programming and Combinatorial Optimization
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem

Cited In (19)

• Primal Heuristics for Branch-and-Price Algorithms
• The multi-terminal vertex separator problem: branch-and-cut-and-price
• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• Stabilized Branch-and-Price for the Rooted Delay-Constrained Steiner Tree Problem
• The generalized dependency constrained spanning tree problem
• A branch-and-price-and-cut method for computing an optimal bramble
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem
• A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
• Polyhedral approach to weighted connected matchings in general graphs
• Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Cost optimized design for the local wind turbine grid of an onshore wind farm
• A unifying model for locally constrained spanning tree problems
• Exact algorithms for finding constrained minimum spanning trees
• Comparison of algorithms for the degree constrained minimum spanning tree
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs

Uses Software

• SteinLib

This page was built for publication: Branch-and-cut-and-price algorithms 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 Q263164)