Problema de cobertura por vértices em redes complexas

• Ano de defesa: 2013
• Autor(a) principal: Silva, Mariana Oliveira da
• Orientador(a): Silva, Murilo Vicente Gonçalves da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Curitiba
• Programa de Pós-Graduação: Programa de Pós-Graduação em Computação Aplicada
• Palavras-chave em Português: Teoria dos grafos; Algorítmos; Otimização combinatória; Complexidade computacional; Computação; Graph theory; Algorithms; Combinatorial optimization; Computational complexity; Computer science
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/734

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas.