.png){kind=icon}
.png){kind=icon}
Return
A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.11.010.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a connected undirected graph G = (V, E), the Minimum Branch Vertices Problem (MBVP) asks for a spanning tree of G with the minimum number of vertices having degree greater than two in the tree. These are called branch vertices. This problem, with applications in the context of optical networks, is known to be NP-hard. We model the MBVP as an integer linear program, with undirected variables, we derive valid inequalities and we prove that some of these are facet defining. We then develop a hybrid formulation containing undirected and directed variables. Both models are solved with branch-and-cut. Comparative computational results show the superiority of the hybrid formulation. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Spanning tree
Branch vertices
Branch-and-cut
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
View more organizations