Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/6146
Title: Análise Experimental dos Algoritmos Exatos Aplicados ao Problema da Árvore Geradora Multiobjetivo
Other Titles: Experimental Analysis of Exact Algorithms Applied to the Multi-objective Spanning Tree Problem
Authors: Fernandes, Islame Felipe da Costa
Keywords: Árvore Geradora, Problemas Multiobjetivo, Algoritmos Exatos.;Spanning Tree, Multi-objective Problems, Exact Algorithms
Issue Date: 25-Nov-2016
Publisher: Universidade Federal do Rio Grande do Norte
Citation: FERNANDES, I. F. C. Análise Experimental dos Algoritmos Exatos Aplicados ao Problema da Árvore Geradora Multiobjetivo. 2016. Monografia de Graduação (Bacharel em Ciência da Computação), UFRN (Universidade Federal do Rio Grande do Norte), Natal, Brasil
Portuguese Abstract: O Problema da Árvore Geradora Multiobjetivo (AGMO) é uma generalização do Problema da Árvore Geradora Mínima. Embora este último possua algoritmo polinomial que o solucione, o mesmo não acontece para sua generalização. Assim como sua versão mono-objetivo, o problema multiobjetivo possui inúmeras aplicações nas mais variadas áreas. Além disso, ele modela situações onde existe a ocorrência de objetivos conflitantes, o que é comum em situações reais. O problema da AGMO é classificado como NP-difícil e vem sendo intensamente explorado na literatura. Diversos algoritmos exatos foram propostos para o problema segundo diferentes técnicas. Alguns destes algoritmos foram analisados em trabalhos anteriores para problemas com 2 objetivos. Este trabalho complementa os trabalhos anteriores, apresentando uma análise dos algoritmos exatos existentes até o momento para o problema da AGMO. São reportados resultados de experimentos computacionais em grafos completos e grade com até 100 vértices para instâncias com 2 objetivos.
Abstract: The Multi-objective Spanning Tree Problem (MSTP) is a generalization of the Minimum Spanning Tree Problem. Although, there are polynomial time algorithms to solve the latter problem, the same is not true for its generalization. Alike the mono-objective version, the multi-objective problem has several real world applications in several areas. Besides, it models situations where there are conflicting criteria, which is a common fact in real situations. The MSTP is classified as NP-hard and has been extensively explored in the literature. Several exact algorithms have been proposed to this problem which are based on different techniques. Some of these algorithms were analyzed in previous works for problems with two objectives. This work complements the previous works, presenting analyses of the exact algorithms proposed up to this moment to the MSTP. Results from computational experiments are reported to complete and grid graphs with up to 100 vertices for 2-objective instances.
URI: http://monografias.ufrn.br/jspui/handle/123456789/6146
Other Identifiers: 2012912437
Appears in Collections:Ciência da Computação

Files in This Item:
File Description SizeFormat 
ArvoreGeradora_Fernandes_2016.pdfMonografia3.23 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons