法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传# o) g" W* j3 h! z/ V2 n
统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面
网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问8 l A# K4 K1 }' Y6 ^6 e! R0 F F; y
题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从
并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点
和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.
关键词 平面网络; 最大流; 最小截; P- 完全; NC
. f/ n0 ?, y" s
$ J2 g) }$ a/ }3 s
1 N$ f6 K9 A; U5 m
( K- d6 k2 c1 {- U) M& f* t+ o9 t
( b+ Y# h7 V _0 l9 b! h$ T
" D/ B3 A, X5 G* h, `, j
. ]$ Q' {% g5 S* j9 O- i
节点和边都有容量的有向平面网络中的最小截和最大流.pdf
(1.26 MB, 下载次数: 0)
# y& l; y6 m2 b/ u