A meta-heuristic for solving the problem of the generating tree with a minimum number of branch vertices

The problem of Minimizing Branch Vertices in a Generating Tree (MBV) consists in, given a connected, undirected and unweighted graph, identifying a generating tree that minimizes the number of vertices with a degree greater than 2. The work investigates the relationship between the density of the graph and the number of vertices with degree greater than 2 in the solutions. The proposed methodology combines density analysis with PageRank centrality to guide a new constructive algorithm, integrated with meta-heuristics such as Multi-Start and Greedy Randomized Adaptive Search Procedure (GRASP), aiming at a more efficient search for solutions. The computational experiments carried out on known instances of the problem show the effectiveness of the proposal to achieve high-quality solutions.