论文部分内容阅读
设G=(N，A，u)是一个顶点集为N，弧集为A，始点为s∈N，终点为t∈N，有限容量向量u={u<,ij>：(i，j)∈A}及正整数K的网络。一个基本K-通道流是一个从始点s∈N到终点t∈N的K个单位流，使得在每个弧上的流是0或1。一个K-通道流是一个从s到t的流，使得这个流可以表示成基本K-通道流的非负线性组合的流。因此，K-通道流问题是求解从s到t不仅要满足顶点平衡(s和t除外)和弧的容量限制下通常的最大流问题，而且这个流必需满足沿着K条弧不交的s-t路发送。在本文中，我们给出了另一个解决K-通道流问题组合算法，分析了这个改进算法的时间复杂性，并且研究了这个算法在理论上的迭代步数少于Kishimoto算法和Newton算法的迭代步数，但不少于原始对偶算法的迭代步数。另外，简要地介绍了K-通道流从弧流形式到路流形式的转化算法。