Título: Árvore Geradora com Dependências Mínima

Data: 31/05/2016 Horário: 13:30h Local: Sala de Seminários do Bloco 952

Resumo:

O problema de Árvore Geradora com Dependências de Custo Mínimo, \textbf{AGDM}$(G, D, w)$, consiste em encontrar a árvore geradora do grafo $G(V, E)$ que satisfaz as restrições de dependência impostas pelo digrafo $D(E, A)$ e que tenha custo mínimo. Em outras palavras, uma aresta $e$ faz parte de uma solução de \textbf{AGDM}$(G, D, w)$ se não existem arcos chegando em $e$ ou se uma outra aresta $e'$ também faz parte da mesma solução e existe um arco $(e', e)$ em $D$. Aqui, provamos que encontrar uma solução viável para \textbf{AGDM}$(G, D, w)$ é \textbf{NP-completo} mesmo quando $G$ é um cacto cordal ou quando $G$ é bipartido e as restrições de dependência ocorrem apenas entre arestas adjacentes. Exibimos também alguns modelos lineares inteiros para o problema, além de algumas desigualdades válidas. Enunciamos também heurísticas para o problema e seus resultados computacionais. Por fim, apresentamos uma técnica de resolução que melhora o tempo de execução.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
• Prof. Dr. Tibérius de Oliveira e Bonates (DEMA/UFC)
• Prof. Dr. Leonardo Sampaio Rocha (UECE)