Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/509
Registro completo de metadados
Campo DCValorIdioma
dc.creatorSakamoto, Rodrigo Cesar-
dc.date.accessioned2011-09-15T13:43:00Z-
dc.date.available2021-09-30T19:56:19Z-
dc.date.issued2011-
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/509-
dc.description.abstractMuitos 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.pt_BR
dc.language.isoporpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectTeoria dos Grafospt_BR
dc.subjectAlgoritmos e Estruturas de Dadospt_BR
dc.subjectAlgoritmos Úteis e Específicospt_BR
dc.subjectProgramação Paralelapt_BR
dc.titleImplementações de algoritmos FPT para o problema do 3-Hitting Set utilizando Clusters e grades computacionaispt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Mongelli, Henrique-
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 
Rodrigo Cesar Sakamoto.pdf1,06 MBAdobe PDFThumbnail
Visualizar/Abrir


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