| 沿通路送流的两个新算法 |
| |
| 引用本文： | 卢爱国,吴新余.沿通路送流的两个新算法[J].南京邮电大学学报(自然科学版),1989(1). |
| |
| 作者姓名： | 卢爱国 吴新余 |
| |
| 作者单位： | 南京邮电学院基础课部，南京邮电学院基础课部 |
| |
| 摘 要： | 本文证明对满足一定约束条件的一类无耗网络,应用沿通路送流法,可获得一个有效的求多商品流算法,其运算复杂度仅为 Od_(pr,max)|E(P_((?),max))|(n k-1)],并且当流网络中各边容量及各源汇对间传输要求量均为整数的情况下,可获得整数流解.本文还将上述算法推广到有耗网络中多商品流的求解问题,提出并证明了平面有耗网中多商品流存在的充分条件,据此获得一个求有耗网络多商品流的多项式时间算法.
|
| 关 键 词： | 网络图论 图论算法 多种物资流 线性规划 |
Two New Algorithms in Terms of Method of Transmitting Flow along Paths |
| |
| Lu Aiguo Wu Xinyu.Two New Algorithms in Terms of Method of Transmitting Flow along Paths[J].Journal of Nanjing University of Posts and Telecommunications,1989(1). |
| |
| Authors: | Lu Aiguo Wu Xinyu |
| |
| Institution: | Basic Division |
| |
| Abstract: | This paper deals with the multicommodity flows.We prove that if the lossless network considered here satisfies a certain condition,we can obtain a very effective algorithm for finding the multicommodity flows by using the method of transmitting flows along the paths,the upper bound of which is Od_(pr,maax) |E(P_(le,max))|(n k-1)].This paper also discusses how to find the multicommodity flows in a lossy network.We show a suffi- cient condition for the multieommodity flows to exist.In accor- dance with this condition,we offer a polynomial-time algorithm for finding flows in the lossy networks. |
| |
| Keywords: | Network graph theory Graph theory algorithm Multicommodity flow Linear programming |
| 本文献已被 CNKI 等数据库收录！ |
|
