Algorithms for the Minimum Branch Vertices Spanning Tree Problem

Given a connected and undirected graph G = (V,E), the Minimum Branch Vertices Spanning Tree Problem (MBV) consists of finding a spanning tree from G that has the fewest vertices with degree greater than 2. As this problem is NP-hard, it is not feasible to solve it exactly in a timely manner, unless P = NP. It is therefore necessary to use heuristic techniques to find solutions with satisfactory quality. This article presents adaptations of algorithms proposed in the literature for this problem, covering constructive heuristics, local searches and meta-heuristics. The results obtained by the constructive algorithms were equivalent to those of the constructive heuristics available in the literature, while the meta-heuristics did not surpass, but came close to the state of the art.