Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275511
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: O problema da árvore geradora com muitas folhas
Title Alternative: The maximum leaf spanning tree problem
Author: Reis, Márcio Félix, 1986-
Advisor: Lee, Orlando, 1969-
Abstract: 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
Subject: Algoritmos de aproximação
Algoritmos em grafos
Otimização combinatória
Editor: [s.n.]
Date Issue: 2014
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Reis_MarcioFelix_M.pdf1.94 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.