时变网络最大流问题的过剩流量收缩算法

时变最大流问题是最大流问题的一个推广．设图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）是任意的非负整数．提出了该问题的一个过剩流量收缩算法，并讨论了这个算法的复杂度．最后，给出了一个数值算例。

An excess scaling algorithm for the time-varying maximum fow problem

The time -varying maximum flow problem is an extension of the classical maximum flow problem. Let G(N,A,b,l) be a network without parallel arcs and loops, where N is the set of nodes, A is the set of arcs, b(i,j,t) is the transit time needed to traverse arc (i,j)∈A, l(i,j,t) is the capacity of arc (i,j). Bothb(i,j,t) andl(ij,t) are functions of the departure time t, where t= 0, 1,2,... ,T, and T > 0 is a given number. The problem is to send the flow as much as possible from the source node to the sink node no later than the time limit T. We assume that b is a pos-itive integer, l is a nonnegative integer and waiting at any node is prohibited except the source node. The problem is known to be NP - complete. An excess scaling algorithm is proposed for solving the problem in O(nmT2 + n2T2 log U)time, where n is the number of nodes, m is the number of arcs, and U is the maximal arc capacity in G.