Name
Title | ||
|---|---|---|
A strong symmetric formulation for the Min-degree Constrained Minimum Spanning Tree Problem |
Abstract | ||
|---|---|---|
Given an integer K≥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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.endm.2016.03.031 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Min-degree minimum spanning tree,Branch-and-cut,valid inequalities | Discrete mathematics,Combinatorics,Minimum degree spanning tree,Distributed minimum spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Shortest-path tree,Kruskal's algorithm,Mathematics,Minimum spanning tree | Journal |
Volume | ISSN | Citations |
52 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre Salles da Cunha | 1 | 242 | 22.32 |
| Luidi Simonetti | 2 | 152 | 15.82 |
| Abilio Lucena | 3 | 362 | 34.05 |