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

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.