论文部分内容阅读
本文证明对满足一定约束条件的一类无耗网络,应用沿通路送流法,可获得一个有效的求多商品流算法,其运算复杂度仅为 O[d_(pr,max)|E(P_((?),max))|(n+k-1)],并且当流网络中各边容量及各源汇对间传输要求量均为整数的情况下,可获得整数流解.本文还将上述算法推广到有耗网络中多商品流的求解问题,提出并证明了平面有耗网中多商品流存在的充分条件,据此获得一个求有耗网络多商品流的多项式时间算法.