Mostrar registro simples

dc.contributor.advisorCarmo, Renato Jose da Silva, 1965-pt_BR
dc.contributor.authorCabral Filho, Edgar de Oliveirapt_BR
dc.contributor.otherVignatti, André Luíspt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informáticapt_BR
dc.date.accessioned2017-05-16T16:53:16Z
dc.date.available2017-05-16T16:53:16Z
dc.date.issued2016pt_BR
dc.identifier.urihttp://hdl.handle.net/1884/45019
dc.descriptionOrientador : Prof. Dr. Renato José da Silva Carmopt_BR
dc.descriptionCoorientador : Prof. Dr. André Luís Vignattipt_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, 26/02/2016pt_BR
dc.descriptionInclui referências : f. 55-57pt_BR
dc.description.abstractResumo: A teoria dos grafos é um ramo da matemática utilizada para modelar e representar um conjunto de elementos e suas relações, além de ser muito utilizada na resolução de problemas computacionais. Um grafo pode representar diversos sistemas naturais e digitais como ligações proteicas, redes sociais, conexões digitais, entre outras. Essas redes contêm diversas características, uma dessas é a distribuição de grau dos vértices. Muitos grafos do mundo real apresentam em sua estrutura uma distribuição de grau que segue uma lei de potência (Power Law), o que informalmente significa que existem poucos vértices de grau elevado, enquanto muitos vértices apresentam grau baixo. Dentro dos problemas clássicos algorítmicos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos e que pertencem à classe NP-Difícil, especificamente o problema da cobertura por vértices mínima em grafos que apresentam uma distribuição de grau lei de potência. Assim, é apresentado neste trabalho um método inspirado em regras de redução ao núcleo do problema. Os resultados obtidos sugerem ser uma boa heurística de aproximação da solução _ótima, além de reduzir significativamente o tempo computacional na resolução do problema da cobertura por vértices. Palavras-chave: Grafos, Cobertura por Vértices, Regras de redução, Lei de Potência.pt_BR
dc.description.abstractAbstract: Graph theory is a branch of mathematics used to model and represent a set of elements and their relationships, which is also often used to solve computational problems. A graph can represent various natural and digital systems, such as: protein binding, social networks, digital connections, among others. Those networks contain diverse characteristics, which one of these is the degree of the distribution of the vertices. Many graphs of the real world have in their structure a degree of distribution following a power-law, where informally means that there are few high degree vertices, while many other vertices have a low degree. Within the algorithmic classic problems, we are interested in computationally difficult problems to be solved and which belong to the NP-Hard class, specifically the problem of minimum vertex cover in graphs, that have a power-law degree distribution. Thus, this work presents a method based on reduction rules to the core of the problem. The achieved results indicate that it is a good approximation heuristic from the optimal solution, in addition to be a technique that a significantly reduces on the computational time to solve the problem of minimum vertex cover. Keywords: Graph, Vertex Cover, reduction rules, Power Law.pt_BR
dc.format.extent57 f. : il., algumas color.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.relationDisponível em formato digitalpt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectAlgoritmospt_BR
dc.subjectTesespt_BR
dc.titleCobertura por vértices mínima em grafos lei de Potênciapt_BR
dc.typeDissertaçãopt_BR


Arquivos deste item

Thumbnail

Este item aparece na(s) seguinte(s) coleção(s)

Mostrar registro simples