Paper Info
Title
The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm.
Abstract
Given an edge weighted undirected graph G and a positive integer d, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of G, such that each vertex is either a leaf or else has degree at least d in the tree. In this paper, we discuss two formulations for MDMST based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming (LP) bounds with other bounds in the literature. Aiming to overcome the fact that the strongest of the two models, the directed one, is not symmetric with respect to the LP bounds, we also presented a symmetric compact reformulation, devised with the application of an Intersection Reformulation Technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds is very time consuming. Thus, better computational results were obtained by a Branch-and-cut algorithm based on the original directed formulation. With the proposed method, several new optimality certificates and new best upper bounds for MDMST were provided.
Year
DOI
Venue
2014
10.1016/j.dam.2011.08.008
Discrete Applied Mathematics
Keywords
Field
DocType
min-degree constrained minimum spanning,computational result,new best upper bound,symmetric compact reformulation,linear programming,intersection reformulation technique,tree problem,branch-and-cut algorithm,undirected graph,new optimality certificate,branch and cut,combinatorial optimization
Discrete mathematics,Combinatorics,k-minimum spanning tree,Prim's algorithm,Algorithm,Euclidean minimum spanning tree,Spanning tree,Gomory–Hu tree,Kruskal's algorithm,Reverse-delete algorithm,Mathematics,Minimum spanning tree
Journal
Volume
ISSN
Citations 
164
0166-218X
5
PageRank 
References 
Authors
0.51
21
2
Name
Order
Citations
PageRank
Leonardo Conegundes Martinez1201.89
Alexandre Salles da Cunha224222.32