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

• 作者: 张宪超 江贺 陈国良
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 平面网络 最大流 最小截 P-完全 NC
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 544-551
• 页数: 8页
• 分类号: TP393
• 字数: 7598字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2006.04.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与技术系	123	2142	20.0	43.0
2	张宪超	大连理工大学软件学院	29	428	12.0	20.0
3	江贺	大连理工大学软件学院	47	513	12.0	21.0