Algoritmos para o Problema da Árvore Geradora com Quantidade Mínima de Vértices Branch

Dado um grafo conexo e não direcionado G = (V,E), o problema da Árvore Geradora com Quantidade Mínima de Vértices Branch (MBV) consiste em encontrar uma árvore geradora de G que possua a menor quantidade de vértices com grau maior que 2. Como esse problema é NP-hard, é inviável resolvê-lo de forma exata num tempo hábil, a não ser que P = NP. Portanto, é necessário a utilização de técnicas heurísticas para encontrar soluções com qualidade satisfatória. Este artigo apresenta adaptações de algoritmos propostos na literatura para este problema, abordando heurísticas construtivas, buscas locais e meta-heurísticas. Os resultados obtidos pelos algoritmos construtivos apresentaram resultados equivalentes em relação as heurísticas construtivas já existentes na literatura, enquanto as meta-heurísticas não superaram, mas se aproximaram do estado da arte.