  Given a graph $G=(V,E)$, the minimum branch vertices problem consists in
finding a spanning tree $T=(V,E')$ of $G$ minimizing the number of vertices
with degree greater than two. We consider a simple combinatorial lower bound
for the problem, from which we propose a decomposition approach. The motivation
is to break down the problem into several smaller subproblems which are more
tractable computationally, and then recombine the obtained solutions to
generate a solution to the original problem. We also propose effective
constructive heuristics to the problem which take into consideration the
problem's structure in order to obtain good feasible solutions. Computational
results show that our decomposition approach is very fast and can drastically
reduce the size of the subproblems to be solved. This allows a branch and cut
algorithm to perform much better than when used over the full original problem.
The results also show that the proposed constructive heuristics are highly
efficient and generate very good quality solutions, outperforming other
heuristics available in the literature in several situations.
