Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm

DOI10.1016/J.ENDM.2010.05.040MaRDI QIDQ2883578zbMATH OpenOpenAlexFDO

Authors Alexandre Salles da Cunha, Leonardo Conegundes Martinez

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.040

zbMATH Keywords

branch-and-cutmin-degree constrained minimum spanning tree problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• A branch and cut method for the degree-constrained minimum spanning tree problem
• 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
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints

Cites work

• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Solving Steiner tree problems in graphs to optimality
• VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Cited in

(11)

• A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
• Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Formulations and branch-and-cut algorithm for the K-rooted mini-max spanning forest problem
• Relax-and-cut as a preprocessor and warm starter to branch-and-cut
• Lower and upper bounds for the degree-constrained minimum spanning tree 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
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints

Describes a project that uses

Uses Software

• SteinLib

This page was built for publication: Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm

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