A decomposition algorithm for multi-terminal networks flows
A decomposition algorithm for multi-terminal networks flows
复制标题
一种多终端网络流分解算法
DOI：
10.1016/0166-218x(86)90080-6
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
T. C. Hu
中科院分区：
文献类型：
--
作者：
M. Shing;T. C. Hu
对于任何具有 n 个顶点和 O(n2) 边的大型网络，直接方法将网络视为一个整体，并花费 O(n4) 时间找到所有顶点对之间的最大流值。一个大的网络有时可以分为三连接的组件。本文引入了一种分解算法来利用这种情况。对于任何具有顶点、O(n2) 条边和 ptri 连接组件的网络 N，每个组件中的顶点数量大致相等，分解算法需要 O(n4/p3+n2) 时间来计算 (2n) 最大流值，这是对 O(n4) 时间直接方法的改进。
For any large networkNwithnvertices and O(n2) edges, the direct approach treats the network as a whole and takes O(n4) time to find the maximum flow values between all pairs of vertices. A large network can sometimes be divided into tri-connected component. In this paper, a decomposition algorithm is introduced to take advantage of the situation. For any networkNwhich hasnvertices, O(n2) edges andptri-connected components, with approximately equal numbers of vertices in each component, the decomposition algorithm required O(n4/p3+n2) time to compute the (2n) maximum flow values, an improvement over the O(n4) time direct approach.