Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/458
Tipo: Dissertação
Título: Implementações alternativas FPT BSP/CGM para o problema k-Cobertura por Vértices
Autor(es): Aguena, Deiviston da Silva
Abstract: Muitas das aplicações do mundo real requerem soluções para problemas NP-Completos. A inexistência de algoritmos polinomiais conhecidos para resolvê-los resulta na grande variedade de propostas de soluções. Estas soluções utilizam principalmente heurísticas e algoritmos de aproximação. Uma abordagem alternativa é a utilização de algoritmos FPT (Fixed Parameter Tractability). Enquanto as técnicas baseadas em heurísticas e em algoritmos de aproximação relaxam a busca por soluções ótimas ou exatas, mas usualmente insistem em algoritmos de tempo polinomial, as técnicas que utilizam algoritmos FPT sempre encontram resultados exatos, mas podem apresentar soluções eficientes na teoria, embora inviáveis na prática. Para controlar o tempo de processamento, os algoritmos FPT possuem um parâmetro k associado à instânica do problema que resolvem. Neste sentido, pequenos valores configurados no parâmetro k produzem soluções polinomiais. Mas, como nem sempre, pequenos valores no parâmetro são suficientes para suprir a real necessidade de um problema, estratégias como utilizar o paralelismo tem sido pesquisadas com objetivo de melhorar tanto o tempo de resposta quanto ao tamanho da instânica do problema que pode ser resolvida. Neste trabalho, estaremos interessados na pesquisa de algoritmosFPT e na implementação eficiente destes algoritmos utilizando o poder do paralelismo no modelo BSP/CGM para diferentes abordagens do problema NP-Completo k-Cobertura por Vértices (k-Vertex Cover).
Palavras-chave: Polinômios
Algoritmos
Ciência da Computação
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/458
Data do documento: 2009
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 
Deiviston da Silva Aguena.pdf641,95 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.