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

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

作　　者：喻文华[1] 沙丹[2] 

机构地区：[1]上海师范大学数理信息学院,上海200234 [2]上海对外贸易学院国际经贸学院,上海201620

出　　处：《上海师范大学学报（自然科学版）》2008年第3期238-248,共11页Journal of Shanghai Normal University(Natural Sciences)

基　　金：Shanghai Municipal Education Commission with project(5Z1206)

摘　　要：时变最大流问题是最大流问题的一个推广.设图G=(V,A)是一个有向图且有唯一的发点s和收点ρ.图G中的每条弧(i,j)∈A都带有两个参数:弧上流的传送时间b(i,j,u)和弧的容量l(i,j,u),它们都是时间u的函数.时变最大流问题就是找出从s到ρ满足容量约束的最大流,并要求此最大流的传送时间不能超过一个预先给定的时间限制T.假设:除发点外,流在其他任何顶点都不能等待;b(i,j,u)是正整数;l(i,j,u)是任意的非负整数.提出了该问题的一个过剩流量收缩算法,并讨论了这个算法的复杂度.最后,给出了一个数值算例.The time - varying maximum flow problem is an extension of the classical maximum flow problem. Let G（N,A,b,I） be a network without parallel arcs and loops, where Nis the set of nodes, A is the set of arcs, b（i,j,t） is the transit time needed to traverse arc （ i ,j） e A, l（ i ,j, t） is the capacity of arc （ i ,j）. Both b （ i ,j, t） and l （ i ,j, 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 positive 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（ nmT^2 ＋ n^2 T^2 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.

关 键 词：最大流 过剩流量收缩算法 时变网络 最优化 

分 类 号：O221.7[理学—运筹学与控制论]