All-Pairs Min-Cut in Sparse Networks
All-Pairs Min-Cut in Sparse Networks
复制标题
稀疏网络中的全对最小割
DOI：
10.1006/jagm.1998.0961
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
C. Zaroliagis
中科院分区：
文献类型：
--
作者：
S. Arikati;S. Chaudhuri;C. Zaroliagis
呈现界限和稀疏网络中的全对切割问题的算法。尤其是在o（n log n）对有限的树宽网络的预处理后，尤其是在计算最小速度的时间之间的权衡。在恒定时间内，任何两个顶点之间的最低点意味着对于此类网络，全对切割问题可以在时间O（N2）中求解。稀疏网络的算法取决于输入网络的拓扑特性。最小切割可以在时间O（N+γ2logγ）中找到，并且可以在时间O（N2+γ4logγ）中求解全对切割。
Algorithms for the all-pairs min-cut problem in bounded tree-width and sparse networks are presented. The approach used is to preprocess the input network so that, afterwards, the value of a min-cut between any two vertices can be efficiently computed. A tradeoff between the preprocessing time and the time taken to compute min-cuts subsequently is shown. In particular, after O(n log n) preprocessing of a bounded tree-width network, it is possible to find the value of a min-cut between any two vertices in constant time. This implies that for such networks the all-pairs min-cut problem can be solved in time O(n2). This algorithm is used in conjunction with a graph decomposition technique of Frederickson to obtain algorithms for sparse networks. The running times depend upon a topological property γ of the input network. The parameter γ varies between 1 and Θ(n); the algorithms perform well when γ=o(n). The value of a min-cut can be found in time O(n+γ2 log γ) and all-pairs min-cut can be solved in time O(n2+γ4 log γ).