Show simple item record

dc.contributor.advisorGuedes, Andre Luiz Pires, 1966-pt_BR
dc.contributor.authorCubas, Rafael dos Santos, 1983-pt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informáticapt_BR
dc.date.accessioned2021-06-21T20:43:00Z
dc.date.available2021-06-21T20:43:00Z
dc.date.issued2009pt_BR
dc.identifier.urihttps://hdl.handle.net/1884/70196
dc.descriptionOrientador: Prof. Dr. André Guedespt_BR
dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 17/07/2009pt_BR
dc.descriptionInclui referências: p. 59-60pt_BR
dc.descriptionÁrea de concentração: Ciência da Computaçãopt_BR
dc.description.abstractResumo: Neste documento apresentamos três recentes trabalhos no campo de estudos da coloração de grafos. Os algoritmos dos planos de corte, do Branch and Cut e o algoritmo de Lucet. Todos são algoritmos exatos para a coloração e apresentaram excelentes resultados nos testes práticos realizados. No nosso estudo iremos mais afundo nas características de cada trabalho, principalmente no algoritmo de Lucet. Através de uma criteriosa comparação entre os três algoritmos será traçado um panorama geral entre os prós e contras de cada algoritmo, com destaque para o algoritmo de Lucet. Além desta comparação, o trabalho também reporta os resultados dos experimentos práticos realizados com alguns algoritmos de coloração. Palavras-chave: Coloração de Grafos. Lucet. Graph. Teoria de Grafos.pt_BR
dc.description.abstractAbstract: In this document, it will be discussed three recent researches on the graph coloring problem: the Cutting Planes, Branch and Cut and Lucet algorithms. All of them provided exact answers and delivered excellent results in the actual tests. In our research, we have gone deeper into the characteristics of each algorithm, in particular Lucet's algorithm. As a result of a thorough comparison between them, an overview of their pros and cons will be presented, especially of the Lucet's algorithm. In addition to the aforementioned comparison, this research also reports the actual results of some graph coloring algorithms. Keywords: Graph coloring. Lucet. Graph. Graph Theory.pt_BR
dc.format.extent1 arquivo (60 p.) : il. (algumas color.).pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.subjectCiência da Computaçãopt_BR
dc.titleAlgoritmos exatos para coloração de grafospt_BR
dc.typeDissertação Digitalpt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record