Construção Paralela de Árvores de Cortes Utilizando Contrações de Grafo Otimizadas
Abstract
A cut tree is a combinatorial structure that represents the edgeconnectivity between all pairs of nodes of an undirected graph. Cut trees are used in applications to solve graph connectivity problems, graph partitioning and clustering, routing and in the analysis of complex networks, including social networks, biological networks, among others. This paper presents a parallel version of the classical Gomory-Hu cut tree construction algorithm. The Gomory-Hu algorithm makes multiple calls to a minimum cut algorithm. Minimum cuts are computed in contracted graphs obtained from the input graph. This paper presents an efficient strategy to compute the contracted graphs. The proposed strategy allows processes to take advantage of previously contracted graphs instances. The proposed algorithm was implemented using MPI and experimental results are presented for several families of graphs demonstrating the performance gains of the proposed strategy.
References
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.
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.
Published
2015-10-18
How to Cite
MASKE, Charles; COHEN, Jaime; DUARTE JR, Elias.
Construção Paralela de Árvores de Cortes Utilizando Contrações de Grafo Otimizadas. In: BRAZILIAN SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (SSCAD), 16. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 192-203.
DOI: https://doi.org/10.5753/wscad.2015.14283.
