Seminário de Teoria da Computação

            Problema da Árvore Caterpillar Mínima

                     Luidi Simonetti

             Sexta-feira, 31 de outubro de 2008
                     Sala 85  16:00hs


Uma árvore é denominada Caterpillar quando, removidos todos os
vértices folhas, ficamos só com um caminho.  O problema da árvore
Caterpillar mínima consiste em encontrar uma árvore geradora de um
grafo que seja Caterpillar e com o menor custo possível.
Apresentaremos métodos de resolução exato e heurístico.