A strong symmetric formulation for the min-degree constrained minimum spanning tree problem

DOI10.1016/j.endm.2016.03.031zbMath1351.90069OpenAlexW2401420742MaRDI QIDQ325449

Mohammad Hasan, M. Dambrine

Publication date: 18 October 2016

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

zbMATH Keywords

branch-and-cut algorithmvalid inequalitiesmin-degree minimum spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Linear programming (90C05)

Cites Work

• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• VNS and second order heuristics for the min-degree constrained minimum spanning tree problem
• Strong lower bounds for the prize collecting Steiner problem in graphs
• The multi-weighted Steiner tree problem: A reformulation by intersection
• md-MST is NP-hard for
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem

This page was built for publication: A strong symmetric formulation for the min-degree constrained minimum spanning tree problem