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

DOI10.1007/s10589-015-9788-7zbMath1343.90101OpenAlexW1747465883MaRDI QIDQ263164

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

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)

Related Items (7)

The generalized dependency constrained spanning tree problem ⋮ Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem ⋮ Cost optimized design for the local wind turbine grid of an onshore wind farm ⋮ Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ A unifying model for locally constrained spanning tree problems ⋮ Exact algorithms for finding constrained minimum spanning trees

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree 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
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Trees and Cuts
• Topological design of centralized computer networks—formulations and algorithms
• A note on genetic algorithms for degree-constrained spanning tree problems
• Solving Steiner tree problems in graphs to optimality
• Solution of a Large-Scale Traveling-Salesman Problem
• Spanning tree manipulation and the travelling salesman problem
• Integer Programming and Combinatorial Optimization
• Benchmarking optimization software with performance profiles.

This page was built for publication: Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem