Banca de QUALIFICAÇÃO: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.

DISCENTE: PATRÍCIA MEDYNA LAURITZEN DE LUCENA DRUMOND

DATA: 01/08/2011

HORA: 09:00

LOCAL: sala de reuniões DIMAp

TÍTULO:

Uma Análise Experimental de Algoritmos Exatos Aplicados ao Problema da Árvore Geradora Multiobjetivo

PALAVRAS-CHAVES:

Árvore geradora multiobjetivo, algoritmo exato, análise experimental

PÁGINAS: 40

GRANDE ÁREA: Ciências Exatas e da Terra

ÁREA: Ciência da Computação

RESUMO:

O Problema da Árvore Geradora Multiobjetivo (AGMO) é uma extensão natural do problema do Problema da Árvore Geradora Mínima com único objetivo. O problema é NP‑árduo e possui aplicação em diversas áreas, por exemplo, no projeto de redes de comunicação. O trabalho apresenta uma análise experimental das diferentes estratégias de algoritmos exatos encontrados na literatura para resolver o problema. As abordagens consideradas para a análise experimental compreendem dois algoritmos utilizando o método duas fases, que diferem apenas na fase 2, um método Branch-and-Bound e duas abordagens baseada em preferências, utilizando os algoritmos de Prim e Kruskal e as integrais de Choquet. Os experimentos computacionais abrangem a comparação do desempenho dos algoritmos levando-se em consideração o tempo de execução, sua eficiência em função do número de objetivos e a quantidade de soluções encontradas em determinado tempo. Para verificar as diferentes abordagens foi investigado o desempenho dos algoritmos em três tipos de instâncias propostas na literatura.

MEMBROS DA BANCA:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA
Interno - 1171465 - MARCELO FERREIRA SIQUEIRA
Interno - 1149561 - MARCO CESAR GOLDBARG