Construção Paralela de Árvores de Cortes Utilizando Contrações de Grafo Otimizadas

• Charles Maske UFPR
• Jaime Cohen UEPG
• Elias Duarte Jr UFPR

DOI: https://doi.org/10.5753/wscad.2015.14283

Resumo

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 especificação de uma estratégia eficiente 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.

Referências

Adamic, L. A. and Glance, N. (2005). The political blogosphere and the 2004 u.s. election: Divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery, pages 36–43. ACM.

Albert, R. and Barabási, A.-l. (2001). Statistical mechanics of complex networks. Reviews of Modern Physics, page 54.

Batagelj, V. and Mrvar, A. Pajek datasets. Disponível para download online em http://vlado.fmf.uni-lj.si/pub/networks/data.

Bollobás, B. (2001). Random Graphs. Cambridge University Press, second edition. Cambridge Books Online.

Chekuri, C. S., Goldberg, A. V., Karger, D. R., Levine, M. S., and Stein, C. (1997). Experimental study of minimum cut algorithms. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '97, pages 324–333, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.

Cohen, J. (2013). Algoritmos Paralelos Para íArvores De Cortes E Medidas De Centralidade Em Grafos. PhD thesis, Universidade Federal do Paraná UFPR.

Cohen, J., Rodrigues, L. A., and Duarte Jr., E. P. (2012). A parallel implementation of In Proceedings of the 2012 IEEE 24th International Symposium on gomory-hu's cut tree algorithm. Computer Architecture and High Performance Computing, SBAC-PAD '12, pages 124–131, Washington, DC, USA. IEEE Computer Society.

Cohen, J., Rodrigues, L. A., Silva, F., Carmo, R., Guedes, A. L. P., and Duarte, E. P. (2011). Parallel implementations of guseld's cut tree algorithm. In Proceedings of the 11th international conference on Algorithms and architectures for parallel processing Volume Part I, ICA3PP'11, pages 258–269, Berlin, Heidelberg. Springer-Verlag.

Duarte Jr, E., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In Dependable Systems and Networks, 2004 International Conference on, pages 495–504.

Engelberg, R., Könemann, J., Leonardi, S., and Naor, J. (2006). Cut problems in graphs with a budget constraint. In LATIN 2006: Theoretical Informatics, volume 3887 of Lecture Notes in Computer Science, pages 435–446. Springer Berlin Heidelberg.

Goldberg, A. V. and Tsioutsiouliklis, K. (1999). Cut tree algorithms. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '99, pages 376–385, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.

Gomory, R. E. and Hu, T. C. (1961). Multi-terminal network ows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570.

Guseld, D. (1990). Very simple methods for all pairs network ow analysis. SIAM Journal on Computing, 19(1):143–155.

Kamath, K. Y. and Caverlee, J. (2011). Transient crowd discovery on the realtime social web. In Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, WSDM '11, pages 585–594. ACM.

Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Algorithmic Aspects of Graph Connectivity. Cambridge University Press.

Nagamochi, H., Ono, T., and Ibaraki, T. (1994). Implementing an efcient minimum capacity cut algorithm. Mathematical Programming, 67(1-3):325–341.

Storchi, G., Dell'Olmo, P., and Gentili, M. (1999). Road network of the city of rome.

Tuncbag, N., Salman, F. S., Keskin, O., and Gursoy, A. (2010). Analysis and network representation of hotspots in protein interfaces using minimum cut trees. Proteins: Structure, Function, and Bioinformatics, 78(10):2283–2294.

Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. 393(June):440–442.