Construção Paralela de Árvores de Cortes Utilizando Contrações de Grafo Otimizadas - Maske, Charles; Cohen, Jaime; Duarte Jr, Elias (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), 2015)
As árvores de cortes representam, de forma compacta, a aresta conectividade de um grafo. Suas aplicações são diversas, incluindo roteamento, avaliação de conectividade, particionamento e agrupamento em grafos, além da análise de redes complexas, incluindo redes sociais, redes formadas a partir de dados biológicos, entre outras. Neste trabalho é apresentada uma versão paralela de um dos algoritmos clássicos para a construção de árvores de cortes, o algoritmo de Gomory-Hu. Este algoritmo faz múltiplas chamadas a um procedimento que encontra um corte de arestas de capacidade mínima entre dois vértices. Para encontrar os cortes mínimos, o algoritmo faz contrações de vértices do grafo de entrada. A principal contribuição do algoritmo apresentado neste trabalho é a especiﬁcação de uma estratégia eﬁciente que permite que processos aproveitem instâncias de grafos contraídos em passos anteriores. O algoritmo proposto foi implementado em MPI e resultados experimentais são apresentados para diversas famílias de grafos, demonstrando os ganhos de desempenho da estratégia proposta.