A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

DOI10.1007/978-3-540-72845-0_29MaRDI QIDQ5432327zbMATH OpenOpenAlexFDO

Authors Markus Behle, Michael Jünger, F. Liers

Publication date 2 January 2008

Published in Experimental Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72845-0_29

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• 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
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• 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

Cited in

(13)

• A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
• Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm
• 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
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• Research on the degree-constrained minimum spanning tree problem based on the Prim algorithm
• Relax-and-cut as a preprocessor and warm starter to branch-and-cut
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• An optimization algorithm for solving degree-constrained minimum spanning tree problems
• Optimality cuts and a branch-and-cut algorithm for the k-rooted mini-max spanning forest problem
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem

This page was built for publication: A Primal Branch-and-Cut Algorithm 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 Q5432327)