کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651596 | 1632579 | 2016 | 8 صفحه PDF | دانلود رایگان |
Given an integer K≥3K≥3 and an edge weighted undirected graph G, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) asks for a minimum cost spanning tree of G, such that every non-leaf vertex has degree at least K. We introduce a new reformulation for MDMST that consists of splitting spanning trees into two parts: a backbone tree spanning only the non-leaf vertices and an assignment of the leaves to non-leaf vertices. The backbone tree is modelled with a lifted version of generalized subtour breaking constraints (GSECs). Our computational results show that we can go beyond the strongest MDMST Linear Programming lower bounds in the literature. In addition, a Branch-and-cut algorithm based on our new lower bounds seems to be competitive with the best MDMST exact approach, despite the lack of a primal heuristic. As a by product, new best lower bounds are provided for several unsolved MDMST instances.
Journal: Electronic Notes in Discrete Mathematics - Volume 52, June 2016, Pages 237–244