Return to search

O problema da árvore geradora com muitas folhas / The maximum leaf spanning tree problem

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:59:09Z (GMT). No. of bitstreams: 1
Reis_MarcioFelix_M.pdf: 1988657 bytes, checksum: 6ee5ea6ba406aea3ccb7e3332e679eab (MD5)
Previous issue date: 2014 / Resumo: Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos / Abstract: In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275511
Date05 August 2014
CreatorsReis, Márcio Félix, 1986-
ContributorsUNIVERSIDADE ESTADUAL DE CAMPINAS, Lee, Orlando, 1969-, Junior, Jose Coelho de Pina, Usberti, Fábio Luiz
Publisher[s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação
Source SetsIBICT Brazilian ETDs
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Format64 f. : il., application/octet-stream
Sourcereponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0022 seconds