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

ゞ_轻描丶幸福的

摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方 8 _5 i) V! A. M5 ^, m* W法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传 ; P. F: X, T7 k7 ?8 Y统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面 : x& q1 }2 P9 B8 H$ E, P1 a5 y网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问 题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从 ) a- G+ @* @, E" g& Z' p并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点 1 u9 m" s6 q$ G/ H和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的. % w% Z) O7 r! M9 d: q9 x3 T# o关键词 平面网络; 最大流; 最小截; P- 完全; NC 0 t. ]' L# r+ S% W* n+ ^3 L& n9 F$ I& i" ^ * k4 ], P' ~4 J0 F6 d. f / c  w& p3 z0 d0 v: H+ \0 t # q5 N* `6 r/ Q- x, V/ f8 v + m4 r3 A2 W: s0 \  ] 1 |* O+ y6 S; e, m 节点和边都有容量的有向平面网络中的最小截和最大流.pdf (1.26 MB, 下载次数: 0) 2014-12-10 10:30 上传 点击文件名下载附件 下载积分: 体力 -2 点 + T! h# J, _' V; s3 ^" }

5 d0 y; W9 c" M6 y; k9 f. e
0 e, i8 b3 g( Z7 f. h1 `$ L