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

ゞ_轻描丶幸福的

摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方 / z  J& D. o% h# G法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传 0 R# ^( m/ ^3 a# r统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面 * F9 F& `' @+ @0 x! p- ~: @网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问 " o" W9 s4 \2 @4 b- w题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从 , O0 `% @1 G' S- v" O/ ]并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点 5 H3 R- R# g9 j" _7 |3 F和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的. 关键词 平面网络; 最大流; 最小截; P- 完全; NC - f5 I# _5 }+ n* r ( J& m9 \+ Q/ g7 _: L  P, T+ f6 i * R! A6 w0 T) i7 Z$ b/ f ) s. D7 t2 }1 ~: R$ r# C ! w7 I( w& z5 N! q : R! p) m- n9 z& H- [9 R 1 T' g* \% T# w! ~ 8 T0 ?' K7 y/ E1 o# Q 节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) 2014-12-10 10:30 上传 点击文件名下载附件 下载积分: 体力 -2 点

, N$ ^- N& }9 X
/ U: F+ u0 b* r