| 摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方! W5 k3 l7 E7 J/ q, d 法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传 统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面 网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问7 z5 Y' V8 M# g1 _; i 题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从* W7 X2 t9 k7 ?* e( ? 并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点' J% ~9 }% T U0 G. D3 _ 和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.( ?. ]* R' |/ W' O 关键词 平面网络; 最大流; 最小截; P- 完全; NC % t; D h/ ^0 H( h 4 u" o% F; D1 M6 M( E7 ~. \& T + N" B* N* j: f% `6 o; T ! U# t3 l+ j; w" H9 c# c. c: n , g/ v6 b3 I( t# s, n. H! @ ; g; T5 s; }9 I6 ^# j0 ^% p
节点和边都有容量的有向平面网络中的最小截和最大流.pdf
(1.26 MB, 下载次数: 0)
|
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |