节点和边都有容量的有向平面网络中的最小截和最大流

ゞ_轻描丶幸福的

摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方 + P9 y8 H/ l, H/ \, U( \# R6 y* V  h法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传 9 N% e0 M1 l2 w. m1 z% @统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面 6 h2 S. g1 I! M& F网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问 题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从 并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点 2 h0 G# i7 e8 w; k和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的. / F% g! d2 i3 u% u7 ], u. D关键词 平面网络; 最大流; 最小截; P- 完全; NC 2 U7 x. ?0 |6 E  g0 ? 7 f8 i& g# v% H* s! ?/ Z) B : O" p* I: B# m7 ]* c( I( L   J  j3 ]7 P0 h6 t 2 b% k$ q' p4 g5 z 节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) 2014-12-10 10:30 上传 点击文件名下载附件 下载积分: 体力 -2 点 & K+ W; ]7 h5 d9 [- W 0 e0 f8 H; ]6 v; R& T/ D! C2 Z

* u4 B0 z3 ^/ Y; T0 V: a, B% g
: |* l- e( `: Z9 U6 q8 B