Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/6146
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorGoldbarg, Elizabeth Ferreira Gouvêa-
dc.contributor.authorFernandes, Islame Felipe da Costa-
dc.date.accessioned2018-03-21T11:35:52Z-
dc.date.available2018-03-21T11:35:52Z-
dc.date.issued2016-11-25-
dc.identifier2012912437pr_BR
dc.identifier.citationFERNANDES, 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, Brasilpr_BR
dc.identifier.urihttp://monografias.ufrn.br/jspui/handle/123456789/6146-
dc.description.abstractThe 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.pr_BR
dc.languagept_BRpr_BR
dc.publisherUniversidade Federal do Rio Grande do Nortepr_BR
dc.rightsopenAccesspr_BR
dc.rightsAn error occurred on the license name.*
dc.rights.uriAn error occurred getting the license - uri.*
dc.subjectÁrvore Geradora, Problemas Multiobjetivo, Algoritmos Exatos.pr_BR
dc.subjectSpanning Tree, Multi-objective Problems, Exact Algorithmspr_BR
dc.titleAnálise Experimental dos Algoritmos Exatos Aplicados ao Problema da Árvore Geradora Multiobjetivopr_BR
dc.title.alternativeExperimental Analysis of Exact Algorithms Applied to the Multi-objective Spanning Tree Problempr_BR
dc.typebachelorThesispr_BR
dc.contributor.referees1Goldbarg, Elizabeth Ferreira Gouvêa-
dc.contributor.referees2Goldbarg, Marco Cesar-
dc.description.resumoO 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.pr_BR
dc.publisher.countryBrasilpr_BR
dc.publisher.departmentCiência da Computaçãopr_BR
dc.publisher.initialsUFRNpr_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpr_BR
dc.contributor.referees3Maia, Silvia Maria Diniz Monteiro-
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