An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices

Rafael A. Melo, Phillippe Samer, Sebastián Urrutia

Given a graph $G=(V,E)$, the minimum branch vertices problem consists in finding a spanning tree $T=(V,E^{\prime })$ of $G$ minimizing the number of vertices with degree greater than two. W…