Implementações de algoritmos FPT para o problema do 3-Hitting Set utilizando Clusters e grades computacionais

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: Sakamoto, Rodrigo Cesar
Orientador(a): Mongelli, Henrique
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufms.br/handle/123456789/509
Resumo: Muitos problemas práticos são NP-Completos e envolvem um grande volume de dados. A busca por soluções exatas, aproximadas ou ótimas para muitos desses problemas resultaram em diversas técnicas engenhosas, visando, principalmente, a complexidade do problema em termos do tamanho da instância do problema. Uma abordagem alternativa para tentar lidar com a intratabilidade computacional de alguns problemas NP-Completos é a Complexidade Parametrizada. Os algoritmos tratáveis por parâmetro fixo, ou mais conhecidos como algoritmos FPT(Fixed Parameter Tractability), exploram a estrutura da instância do problema limitando a aparentemente inevit avel explos~ao combinatorial na solução do problema (a um parâmetro). Neste trabalho será mostrado como combinar o paralelismo e algoritmos FPT, permitindo a utilização de instâncias ainda maiores na soluçãoo de problemas FPT. Mais precisamente, será apresentado um algoritmo FPT paralelo no modelo BSP/CGM para o problema do 3-Hitting Set, uma adaptação do algoritmo FPT paralelo de Cheetham et al., sendo substituído suas fases, pelo algoritmo de Niedermeier e Rossmanith, e uma implementação de tal algoritmo.