Paper Info
Title
The Tree-Star Problem: A Formulation and a Branch-and-Cut Algorithm
Abstract
Let G=(V,E) be a connected undirected graph and assume that an edge e=i,j∈E may be priced differently, at the different spanning trees of G that contain it. A cost ce applying when e is leaf implying, i.e., when e belongs to the spanning tree and i or j are spanning tree leaves. Otherwise, when e belongs to the tree but is not leaf implying, a cost de would apply. Under such a pricing of edges, the Tree-Star Problem is to find a least cost spanning tree of G. The problem does not appear to have been previously investigated in the literature and we show it to be NP-hard, formulate it as a mixed integer program, and propose and test a Branch-and-Cut algorithm for it. So far, the algorithm contains no primal heuristic. However, as it stands, it is already capable of solving to proven optimality tree-star instances with as many as 299 vertices.
Year
DOI
Venue
2016
10.1016/j.endm.2016.03.038
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
The Tree-Star Problem,Formulation,Branch-and-Cut Algorithm
Discrete mathematics,Combinatorics,Minimum degree spanning tree,k-minimum spanning tree,K-ary tree,Algorithm,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Kruskal's algorithm,Minimum spanning tree
Journal
Volume
ISSN
Citations 
52
1571-0653
3
PageRank 
References 
Authors
0.43
3
3
Name
Order
Citations
PageRank
Abilio Lucena136234.05
Luidi Simonetti215215.82
Alexandre Salles da Cunha324222.32