论文部分内容阅读
时变最大流问题是最大流问题的一个推广．设图G=（y，A）是一个有向图且有唯一的发点s和收点P．图G中的每条弧（i，j）∈A都带有两个参数：弧上流的传送时间b（i,j，u）和弧的容量f（i.j.u），它们都是时间u的函数．时变最大流问题就是找出从s到P满足容量约束的最大流，并要求此最大流的传送时间不能超过一个预先给定的时间限制T.假设：除发点外，流在其他任何顶点都不能等待；b（i.j.u）是正整数；l（i.j.u）是任意的非负整数．提出了该问题的一个过剩流量收缩算法，并讨论了这个算法的复杂度．最后，给出了一