[其他资源] 节点和边都有容量的有向平面网络中的最小截和最大流

[复制链接]

字体大小: 正常放大

ゞ_轻描丶幸福的

2802 主题	160 听众	8905 积分

TA的每日心情

	开心 2017-4-26 10:25

签到天数: 491 天

[LV.9]以坛为家II

自我介绍: 即使不开心也不要皱眉，因为你永远不知道有谁会爱上你的微笑！

群组: 数学中国试看培训视频

群组: 2017美赛两天强训

群组: 2015司守奎matlab培训

群组: 2016国赛优秀论文解析

群组: 国赛护航思路养成班

电梯直达

1^#

发表于 2014-12-10 10:30 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

摘要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方
法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传
统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面
网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问
题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从
并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点
和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.
关键词 平面网络; 最大流; 最小截; P- 完全; NC