Tratabilidade por Parâmetros Fixos: Algoritmos e Experimentação no Modelo BSP/CGM

O modelo BSP/CGM é um modelo realístico de computação paralela em que são considerados, além da complexidade de tempo de processamento, o número de vezes em que existe comunicação entre os processadores. As implementações em máquinas paralelas reais dos algoritmos projetados nesse modelo têm obtido tempos bastante próximos aos previstos no modelo. Por outro lado, algoritmos FPT têm sido implementados e constituem uma abordagem promissora na solução de problemas NP-completos que necessitam de soluções exatas e para os quais podemos fixar, na prática, o parâmetro responsável pela explosão combinatorial. A combinação do paralelismo e de algoritmos FPT tem se mostrado profícua na obtenção de soluções para problemas práticos. No projeto de algoritmos FPT, geralmente, utilizamos duas técnicas básicas: redução ao núcleo do problema e árvore limitada de busca. Estas estratégias podem ser combinadas na obtenção de algoritmos FPT. Ambas estratégias podem ser paralelizadas. A paralelização da técnica de árvore limitada de busca mostrou-se bastante eficiente pois multiplicam-se os pontos de busca de soluções. Os principais problemas que serão abordados neste projeto têm algoritmos FPT seqüenciais descritos que utilizam basicamente a estratégia de árvore limitada de busca e são ou têm aplicações em Biologia Computacional e em grafos. Para o problema da k-Cobertura por Vértices, implementamos o algoritmo FPT/CGM de Cheetham et al. e obtivemos tempos muito bons, comparados a outras implementações seqüenciais e paralelas. Os algoritmos desenvolvidos serão implementados utilizando-se a linguacem C/C++ e as bibliotecas MPI e BSP-Lib. Na experimentação utilizaremos clusters de PC e grades computacionais. O objetivo principal deste projeto é o desenvolvimento e implementação de algoritmos paralelos eficientes para problemas FPT, usando modelos realísticos de computação paralela, de modo a comprovar a viabilidade da utilização de algoritmos FPT e computação paralela.

Coordenador: Henrique Mongelli