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

ゞ_轻描丶幸福的

摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方 / l5 S1 H3 t+ o. g法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传 & u' ]% F! c# y( d# B  h统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面 ) w' Q8 k4 P) d8 L0 a$ c& Q网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问 题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从 8 o; l! Y+ Q* a. {! i1 p7 Z- q并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点 和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的. , H9 j3 P4 e# r" h  ?) E关键词 平面网络; 最大流; 最小截; P- 完全; NC 4 T+ x$ U4 B  \4 E / s( m- j$ R8 t& B 1 H0 o; t  g9 _: P6 M: q7 V - }  g5 _$ N( J9 J0 |  y ) @: v8 J* l* Y ; A8 H9 z  x: Q: ^  Z5 p0 h & k4 g# N9 C$ F+ Q9 l' `5 K/ Q4 o! l 节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) 2014-12-10 10:30 上传 点击文件名下载附件 下载积分: 体力 -2 点 1 w/ J5 I0 [/ f3 o

2 y/ j, H& x! `
1 ]- y. k  H, y* R5 |