Formulações e Algoritmos Sequenciais e Paralelos para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo - Martinez, Leonardo Conegundes; Cunha, Alexandre Salles da (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2013)
Dados um grafo não direcionado valorado nas arestas G e um inteiro positivo d, o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo (PAGMGM) consiste em encontrar uma árvore geradora de custo mínimo T de G, tal que o grau de cada vértice em T seja igual a 1 ou maior ou igual a d. Neste trabalho, introduzimos formulações de Programação Inteira e algoritmos de otimização sequenciais e paralelos para o problema. Com os métodos propostos, vários novos certificados de otimalidade e melhores limites inferiores e superiores para o PAGMGM são fornecidos.