|
|||||
|
|
| 节点和边都有容量的有向平面网络中的最小截和最大流 | |
| 引用本文： | 张宪超,江贺,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):544-551. |
| 作者姓名： | 张宪超 江贺 陈国良 |
| 作者单位： | 1. 大连理工大学软件学院,大连,116024 2. 大连理工大学软件学院,大连,116024;中国科学技术大学计算机科学与技术系,合肥,230037 3. 中国科学技术大学计算机科学与技术系,合肥,230037 |
| 摘 要： | 在一般网络中,节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题.但传统转化方法用在平面网络中破坏了网络的平面性,使平面网络中节点和边都有容量的问题比仅边有容量的问题难.使用传统转化方法得到的两个问题的算法复杂度均为O（n2logn）（n表示网络中的节点数）.对此,作者曾给出了无向平面网络中最小截问题的保持平面性的转化方法.在此基础上,这里进一步讨论有向平面网络中的最小截、最大流问题,给出有向网络中保持平面性的转化方法,并利用此转化得到了复杂度均为O（nlogn）的最小截和最大流算法.从并行计算复杂性角度来看,传统方法转化后的问题是P-完全的.而使用新方法可以得到NC算法,且可以证明节点和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC的. |
| 关 键 词： | 平面网络 最大流 最小截 P-完全 |
| 收稿时间： | 2004-10-26 |
| 修稿时间： | 2004-10-262005-12-02 |
Minimum Cuts and Maximum Flows in Directed Planar Networks with Both Node and Edge Capacities |
|
| ZHANG Xian-Chao,JIANG He,CHEN Guo-Liang.Minimum Cuts and Maximum Flows in Directed Planar Networks with Both Node and Edge Capacities[J].Chinese Journal of Computers,2006,29(4):544-551. | |
| Authors: | ZHANG Xian-Chao JIANG He CHEN Guo-Liang |
| Affiliation: | 1.School of Software, Dalian University of Technology, Dalian 116024;2.Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027 |
| Abstract: | |
| Keywords: | NC |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |