Goldbarg, Elizabeth Ferreira GouvêaFernandes, Islame Felipe da Costa2018-03-212021-09-202018-03-212021-09-202016-11-25FERNANDES, 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, Brasilhttps://repositorio.ufrn.br/handle/123456789/34204The 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.openAccessAttribution-NonCommercial-NoDerivs 3.0https://creativecommons.org/licenses/by-nc-nd/3.0/Árvore Geradora, Problemas Multiobjetivo, Algoritmos Exatos.Spanning Tree, Multi-objective Problems, Exact AlgorithmsbachelorThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO