Improved Parallel Implementations of Gusfield’s Cut Tree Algorithm
Resumo
This work presents parallel versions of Gusfield’s cut tree algorithm and the proposal of two heuristics aimed at improving their performance. Cut trees are a compact representation of the edge-connectivity between every pair of vertices of an undirected graph. Cut trees have a vast number of applications in combinatorial optimization and in the analysis of networks originated in many applied fields. However, surprisingly few works have been published on the practical performance of cut tree algorithms. This paper describes two parallel versions of Gusfield’s cut tree algorithm and presents extensive experimental results which show a significant speedup on most real and synthetic graphs in our dataset.
Referências
P. S. Pacheco. A User’s Guide to MPI. University of San Francisco, 1998.
B. Chapman, G. Jost, and R. Van der Pas. Using OpenMP: portable shared memory parallel programming. MIT Press, 2008.
G. Rao, H. Stone, and T. Hu. Assignment of tasks in a distributed processor system with limited memory. IEEE Transactions on Computers, 28:291–299, 1979.
C. Kim. Cut-tree construction for facility layout. Computers & Industrial Engineering, 28(4):721–730, 1995.
L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th international conference on World Wide Web, WWW ’07, pages 181–190, New York, NY, USA, 2007. ACM.
B. Saha and P. Mitra. Dynamic algorithm for graph clustering using minimum cut tree. In Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, pages 667–671, Washington, DC, USA, 2006. IEEE Computer Society.
A. Mitrofanova, M. Farach-Colton, and B. Mishra. Efficient and robust prediction algorithms for protein complexes using gomory-hu trees. In R. B. Altman, A. K. Dunker, L. Hunter, T. Murray, and T. E. Klein, editors, Pacific Symposium on Biocomputing, pages 215–226, 2009.
N. Tuncbag, F. S. Salman, O. Keskin, and A. Gursoy. Analysis and network representation of hotspots in protein interfaces using minimum cut trees. Proteins: Structure, Function, and Bioinformatics, 78(10):2283–2294, 2010.
L. Wu and P. K. Varshney. On survivability measures for military networks. Military Communications Conference, pages 1120–1124, 1990.
C. L. M. M. Grötschel and M. Stoer. Polyhedral and computational investigations for designing communication networks with high survivability requirements. Operations Research, 1995.
H. Saran and V. V. Vazirani. Finding k cuts within twice the optimal. SIAM J. Comput., 24(1):101–108, 1995.
G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Mathematics, 1(4), 2003.
A. Letchford, G. Reinelt, and D. Theis. Odd minimum cutsets and b-matchings revisited. SIAM Journal on Discrete Mathematics, 22(4), 2008.
R. Görke, T. Hartmann, and D. Wagner. Dynamic graph clustering using Minimum-Cut trees. In F. Dehne, M. Gavrilova, J.-R. Sack, and C. T´oth, editors, Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, chapter 30, pages 339–350. Springer Berlin / Heidelberg, Berlin, Heidelberg, 2009.
K. Y. Kamath and J. Caverlee. Transient crowd discovery on the real-time social web. In Proceedings of the 4th ACM Web Search and Data Mining Conference (WSDM), 2011.
R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York, NY, USA, 2008.
D. A. Bader and V. Sachdeva. A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic. In M. J. Oudshoorn and S. Rajasekaran, editors, ISCA PDCS, pages 41–48. ISCA, 2005.
B. Hong and Z. He. An asynchronous multi-threaded algorithm for the maximum network flow problem with nonblocking global relabeling heuristic. IEEE Transactions on Parallel and Distributed Systems, 99(PrePrints), 2010.
A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. J. ACM, 35:921–940, 1988.
B. V. Cherkassky and A. V. Goldberg. On Implementing the Push-Relabel Method for the Maximum Flow Problem. Algorithmica, 19(4):390–410, 1997.
J. K. J. Leskovec and C. Faloutsos. Graph evolution: Densification and shrinking diameters. In ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 2007.
V. Batagelj and A. Mrvar. Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em abril de 2011.
D. J. Watts and S. H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442, 1998.
B. Bollobás. Random Graphs. Cambridge University Press, 2 edition, 2001.
R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74(1):47–97, 2002.
C. S. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. Experimental study of minimum cut algorithms. In SODA ’97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pages 324– 333, PA, USA, 1997. SIAM.
A. V. Goldberg and K. Tsioutsiouliklis. Cut tree algorithms. In SODA ’99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 376–385, Philadelphia, PA, USA, 1999. Society for Industrial and Applied Mathematics.
B. Chapman, G. Jost, and R. Van der Pas. Using OpenMP: portable shared memory parallel programming. MIT Press, 2008.
G. Rao, H. Stone, and T. Hu. Assignment of tasks in a distributed processor system with limited memory. IEEE Transactions on Computers, 28:291–299, 1979.
C. Kim. Cut-tree construction for facility layout. Computers & Industrial Engineering, 28(4):721–730, 1995.
L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th international conference on World Wide Web, WWW ’07, pages 181–190, New York, NY, USA, 2007. ACM.
B. Saha and P. Mitra. Dynamic algorithm for graph clustering using minimum cut tree. In Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, pages 667–671, Washington, DC, USA, 2006. IEEE Computer Society.
A. Mitrofanova, M. Farach-Colton, and B. Mishra. Efficient and robust prediction algorithms for protein complexes using gomory-hu trees. In R. B. Altman, A. K. Dunker, L. Hunter, T. Murray, and T. E. Klein, editors, Pacific Symposium on Biocomputing, pages 215–226, 2009.
N. Tuncbag, F. S. Salman, O. Keskin, and A. Gursoy. Analysis and network representation of hotspots in protein interfaces using minimum cut trees. Proteins: Structure, Function, and Bioinformatics, 78(10):2283–2294, 2010.
L. Wu and P. K. Varshney. On survivability measures for military networks. Military Communications Conference, pages 1120–1124, 1990.
C. L. M. M. Grötschel and M. Stoer. Polyhedral and computational investigations for designing communication networks with high survivability requirements. Operations Research, 1995.
H. Saran and V. V. Vazirani. Finding k cuts within twice the optimal. SIAM J. Comput., 24(1):101–108, 1995.
G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Mathematics, 1(4), 2003.
A. Letchford, G. Reinelt, and D. Theis. Odd minimum cutsets and b-matchings revisited. SIAM Journal on Discrete Mathematics, 22(4), 2008.
R. Görke, T. Hartmann, and D. Wagner. Dynamic graph clustering using Minimum-Cut trees. In F. Dehne, M. Gavrilova, J.-R. Sack, and C. T´oth, editors, Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, chapter 30, pages 339–350. Springer Berlin / Heidelberg, Berlin, Heidelberg, 2009.
K. Y. Kamath and J. Caverlee. Transient crowd discovery on the real-time social web. In Proceedings of the 4th ACM Web Search and Data Mining Conference (WSDM), 2011.
R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York, NY, USA, 2008.
D. A. Bader and V. Sachdeva. A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic. In M. J. Oudshoorn and S. Rajasekaran, editors, ISCA PDCS, pages 41–48. ISCA, 2005.
B. Hong and Z. He. An asynchronous multi-threaded algorithm for the maximum network flow problem with nonblocking global relabeling heuristic. IEEE Transactions on Parallel and Distributed Systems, 99(PrePrints), 2010.
A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. J. ACM, 35:921–940, 1988.
B. V. Cherkassky and A. V. Goldberg. On Implementing the Push-Relabel Method for the Maximum Flow Problem. Algorithmica, 19(4):390–410, 1997.
J. K. J. Leskovec and C. Faloutsos. Graph evolution: Densification and shrinking diameters. In ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 2007.
V. Batagelj and A. Mrvar. Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em abril de 2011.
D. J. Watts and S. H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442, 1998.
B. Bollobás. Random Graphs. Cambridge University Press, 2 edition, 2001.
R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74(1):47–97, 2002.
C. S. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. Experimental study of minimum cut algorithms. In SODA ’97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pages 324– 333, PA, USA, 1997. SIAM.
A. V. Goldberg and K. Tsioutsiouliklis. Cut tree algorithms. In SODA ’99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 376–385, Philadelphia, PA, USA, 1999. Society for Industrial and Applied Mathematics.
Publicado
26/10/2011
Como Citar
COHEN, Jaime; RODRIGUES, Luiz A.; DUARTE JR., Elias P..
Improved Parallel Implementations of Gusfield’s Cut Tree Algorithm. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 12. , 2011, Vitória.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 113-120.
DOI: https://doi.org/10.5753/wscad.2011.17275.
