Técnicas de programação matemática aplicadas ao problema da árvore geradora mínima rotulada

O problema da árvore geradora mínima rotulada (PAGMR) é definido em um grafo não-direcionado $G=(V,E,L)$ com conjunto
de vértices $V$, conjunto de arestas $E$, e conjunto de rótulos $L$. Cada aresta $e=\{i,j\} \in E$ é associada a um custo não-negativo $c_e$ e a um rótulo $l_e \in L$. O PAGMR é NP-Difícil e visa determinar uma árvore
geradora mínima com no máximo $K$ rótulos distintos, onde $K$ é um número inteiro positivo dado como entrada. Neste
trabalho, propomos modelos em programação matemática para o PAGMR, assim como um algoritmo de decomposição de Benders.
Experimentos realizados em instâncias aleatórias indicam que nossas abordagens alcançam melhores resultados
do que os encontrados na literatura. Para valores pequenos de $K$, em particular, o algoritmo de Benders se mostra a mais promissora das técnicas.