dc.contributor | Gouvêa, Elizabeth Ferreira | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/4139401241377019 | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/2888641121265608 | |
dc.contributor | Ramos, Iloneide Carlos de Oliveira | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/0613948277011672 | |
dc.contributor | Cruz Neto, Joao Xavier da | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/9936034232663152 | |
dc.contributor | Siqueira, Marcelo Ferreira | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/7340736676138238 | |
dc.contributor | Goldbarg, Marco César | |
dc.contributor | | |
dc.contributor | http://lattes.cnpq.br/1371199678541174 | |
dc.creator | Drumond, Patricia Medyna Lauritzen de Lucena | |
dc.date.accessioned | 2012-10-15 | |
dc.date.accessioned | 2014-12-17T15:48:01Z | |
dc.date.accessioned | 2022-10-05T22:59:54Z | |
dc.date.available | 2012-10-15 | |
dc.date.available | 2014-12-17T15:48:01Z | |
dc.date.available | 2022-10-05T22:59:54Z | |
dc.date.created | 2012-10-15 | |
dc.date.created | 2014-12-17T15:48:01Z | |
dc.date.issued | 2012-03-05 | |
dc.identifier | DRUMOND, Patricia Medyna Lauritzen de Lucena. An experimental analysis of exact algorithms applied to the multiobjective spanning tree problem. 2012. 85 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2012. | |
dc.identifier | https://repositorio.ufrn.br/jspui/handle/123456789/18047 | |
dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/3944052 | |
dc.description.abstract | The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature | |
dc.publisher | Universidade Federal do Rio Grande do Norte | |
dc.publisher | BR | |
dc.publisher | UFRN | |
dc.publisher | Programa de Pós-Graduação em Sistemas e Computação | |
dc.publisher | Ciência da Computação | |
dc.rights | Acesso Aberto | |
dc.subject | Algoritmos experimentais | |
dc.subject | Algoritmos exatos | |
dc.subject | Árvore geradora multiobjetivo | |
dc.subject | Análise experimental | |
dc.subject | Otimização combinatória | |
dc.subject | Experimental algorithms | |
dc.subject | Exact algorithms | |
dc.subject | Multiobjective spanning tree | |
dc.subject | Experimental analysis | |
dc.subject | Combinatorial optimization | |
dc.title | Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo | |
dc.type | masterThesis | |