Uma meta-heurística para solução do problema da árvore geradora com número mínimo de vértices branch

O problema de Minimizar Vértices Branch em uma Árvore Geradora (MBV) consiste em, dado um grafo conexo, não direcionado e sem pesos, identificar uma árvore geradora que minimize o número de vértices com grau superior a 2. O trabalho investiga a relação entre a densidade do grafo e a quantidade de vértices com grau maior que 2 nas soluções. A metodologia proposta combina análise de densidade com a centralidade PageRank para guiar um novo algoritmo construtivo, integrado a meta-heurísticas como o Multi-Start e o Greedy Randomized Adaptive Search Procedure (GRASP), visando uma busca de soluções mais eficiente. Os experimentos computacionais realizados sobre instâncias conhecidas do problema evidenciam a eficácia da proposta para alcançar soluções de alta qualidade.