Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/461
Tipo: Dissertação
Título: O Problema da k-Cobertura por Vértices: uma Implementação FPT no Modelo BSP/CGM
Autor(es): Hanashiro, Erik Joey
Abstract: Em muitas situacões práticas precisamos resolver problemas NP-completos com exatidão. A Complexidade Parametrizada é um método promissor para lidarmos com a intratabilidade de alguns problemas, principalmente aqueles cuja entrada pode ser dividida em uma parte principal e um parâmetro. A parte principal da entrada contribui polinomialmente na complexidade total do problema, enquanto a aparentemente inevitável explosão combinatorial fica confinada ao parâmetro. Neste trabalho estudamos a teoria sobre Complexidade Parametrizada e o algoritmo FPT paralelo de Cheetham et al. no modelo BSP/CGM para o problema da k-Cobertura por Vértices, e nossa contribuição é apresentar uma implementação refinada e melhorada de tal algoritmo. A escolha de boas estruturas de dados e o uso da técnica de backtracking em nossa implementação foram fundamentais para que obtivessemos tempos paralelos melhores em nossos experimentos. Utilizamos cinco grafos de conflitos referentes a aminoácidos, os mesmos usados por Cheetham et al. em seus experimentos. Mesmo utilizando um ambiente computacional inferior ao usado por Cheetham et al., para dois desses grafos obtivemos tempos aproximadamente 115 vezes melhores, para um deles 16 vezes melhor e, para os grafos restantes obtivemos tempos um pouco melhores. Além disso, para três desses grafos obtivemos coberturas por vértice de tamanho menor.
Palavras-chave: Algoritmos
Teoria dos Grafos
Matemática Aplicada
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/461
Data do documento: 2004
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Erik Joey Hanashiro.pdf713,91 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.