- 在线时间
- 1497 小时
- 最后登录
- 2017-5-18
- 注册时间
- 2014-8-20
- 听众数
- 160
- 收听数
- 0
- 能力
- 70 分
- 体力
- 17832 点
- 威望
- 5 点
- 阅读权限
- 150
- 积分
- 8830
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 3830
- 主题
- 2802
- 精华
- 4
- 分享
- 1
- 好友
- 756
TA的每日心情 | 开心
2017-4-26 10:25 |
|---|
签到天数: 491 天 [LV.9]以坛为家II
- 自我介绍
- 即使不开心也不要皱眉，因为你永远不知道有谁会爱上你的微笑！
 群组: 数学中国试看培训视频 群组: 2017美赛两天强训 群组: 2015司守奎matlab培训 群组: 2016国赛优秀论文解析 群组: 国赛护航思路养成班 |
摘 要 在一般网络中, 节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题. 但传统转化方
, a8 O' {, T7 a2 o8 l7 N法用在平面网络中破坏了网络的平面性, 使平面网络中节点和边都有容量的问题比仅边有容量的问题难. 使用传7 ^' T5 ~0 j: y2 l$ F" n) A, `8 W
统转化方法得到的两个问题的算法复杂度均为O( n2 lo g n) ( n 表示网络中的节点数) . 对此, 作者曾给出了无向平面3 }4 E8 K9 W5 p( `6 }& ]
网络中最小截问题的保持平面性的转化方法. 在此基础上, 这里进一步讨论有向平面网络中的最小截、最大流问2 y/ D2 Y! l0 U' ], q- i3 K
题, 给出有向网络中保持平面性的转化方法, 并利用此转化得到了复杂度均为O( nlog n) 的最小截和最大流算法. 从4 ~- g: E G, m% B; |+ a4 l
并行计算复杂性角度来看, 传统方法转化后的问题是P- 完全的. 而使用新方法可以得到NC 算法, 且可以证明节点
' f9 ~1 ^% R: i和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC 的.' k! f" W- v. J8 q' t
关键词 平面网络; 最大流; 最小截; P- 完全; NC$ b% i0 \! D: ~" S, Y" t
6 c$ [4 x6 F1 _& A- A+ p( t; t$ b) j
7 d! {2 H% c! K/ ~' W+ }1 u% Y C2 \+ r0 o
! O- I1 f5 a4 H0 [* X* H' J) g* K5 Z( L
4 H* f4 g2 @: s- ?9 S& V2 V1 N: b/ k. u
) z) W6 ^& a* |7 e: G S( i
& x" }7 L5 h5 g/ e7 `: K
节点和边都有容量的有向平面网络中的最小截和最大流.pdf
(1.26 MB, 下载次数: 0)
; r$ |# u$ O/ D3 Z
. W( U: {7 c2 j1 Q |
% D& } F! r# j& ^7 _
8 ^! T$ U# }- w& k7 K |
zan
|
IP卡
狗仔卡
发表于 2014-12-10 10:30
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
