Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions
Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions
复制标题
通过高效图收缩加速 Gomory-Hu 并行割树算法
DOI：
10.1007/s00453-019-00658-6
复制
发表时间：
2019
期刊：
影响因子：
1.1
通讯作者：
E. P. Duarte
中科院分区：
文献类型：
--
作者：
Charles Maske;Jaime Cohen;E. P. Duarte
割树是一种组合结构，代表了无向图的所有节点对之间的边缘连接性。切树具有多个可靠性应用程序，因为它们表示断开每个网络节点所需的数量。它们已用于解决其他几个应用程序中的连接问题，路由和分析复杂网络的分析。这项工作介绍了经典的Gomory-Hu割树算法的并行版本。该算法是基于计算合同图上最小切割的任务。主要贡献是计算合同图的有效策略，该策略允许过程利用先前的合同图实例，而不是始终从原始输入图中计算所有收缩。使用MPI实施了该算法，并为几个图表提供了实验结果，并显示出显着的性能增长。
A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of nodes of an undirected graph. Cut trees have multiple applications in dependability, as they represent how much it takes to disconnect every pair of network nodes. They have been used for solving connectivity problems, routing, and in the analysis of complex networks, among several other applications. This work presents a parallel version of the classical Gomory-Hu cut tree algorithm. The algorithm is heavily based on tasks that compute the minimum cut on contracted graphs. The main contribution is an efficient strategy to compute the contracted graphs, that allows processes to take advantage of previously contracted graph instances, instead of always computing all contractions from the original input graph. The proposed algorithm was implemented using MPI and experimental results are presented for several families of graphs and show significant performance gains.