Faster Network Algorithms Based on Graph Decomposition
Faster Network Algorithms Based on Graph Decomposition
复制标题
基于图分解的更快网络算法
DOI：
10.1007/978-3-319-75172-6_8
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sadakane Kunihiko
中科院分区：
文献类型：
--
作者：
Kashyop Manas Jyoti;Nagayama Tsunehiko;Sadakane Kunihiko
我们提出了基于图分解的最大流问题及相关问题的快速算法。我们的算法首先从给定的图中构造索引（数据结构），然后使用它们来解决问题。一个基本问题是一个所有对的最大流问题，它包括两个阶段。在预处理阶段，我们构造索引，在查询阶段，我们使用索引处理查询。利用这些指标可以求解所有的最大流问题和最小割问题。我们的算法的时间复杂度取决于图中的最大三连通分量的大小，sayr。我们的算法运行速度比已知的算法ifris小。最大流问题可以及时解决，这比最好的已知算法[Orlin 2013]更快，如果，其中和分别是顶点和边的数量。
We propose faster algorithms for the maximum flow problem and related problems based on graph decomposition. Our algorithms first construct indices (data structures) from a given graph, then use them for solving the problems. A basic problem is an all pairs maximum flow problem, which consists of two stages. In a preprocessing stage we construct an index, and in a query stage we process the query using the index. We can solve all pairs maximum flow problem and minimum cut problem using the indices. Time complexities of our algorithms depend on the size of the maximum triconnected component in the graph, sayr. Our algorithms run faster than known algorithms ifris small. The maximum flow problem can be solved intime, which is faster than the best knownalgorithm [Orlin 2013] if, wherenandmare the numbers of vertices and edges, respectively.
登录
查看更多内容
使用 SPQR 树在线维护三元连接组件
影响因子：
1.1
作者：
G. Battista;R. Tamassia
通讯作者：
R. Tamassia
DOI：
10.1016/0166-218x(86)90080-6
发表时间：
1986
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
M. Shing;T. C. Hu
通讯作者：
T. C. Hu
通过保留复杂性的映射在自由树上进行计算
影响因子：
1.1
作者：
B. Chazelle
通讯作者：
B. Chazelle
稀疏网络中的全对最小割
DOI：
10.1006/jagm.1998.0961
发表时间：
1995
期刊：
--
影响因子：
--
作者：
S. Arikati;S. Chaudhuri;C. Zaroliagis
通讯作者：
C. Zaroliagis
DOI：
--
发表时间：
1995
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
A. Benczúr
通讯作者：
A. Benczúr