The Maximum Flow in a Time-Varying Generalized
Network

Dan Sha, Xiaoqiang Cai, and C. K. Wong
Department of Applied Mathematics, Shanghai Normal University,
Shanghai 200234, P.R. China

Abstract

In this paper, we study a new problem which finds a maximum flow in a time-varying generalized network. In such a network, a flow must take a transit time to traverse an arc. Moreover, this transit time, together with the arc capacity, the vertex capacity, and the arc multiplier are all the functions of the departure time t at the beginning vertex of the arc, where t=0,1,...,T and T>0 is a given number. Waiting at a vertex is allowed. The problem is to find a schedule to send a given flow v from the source to the sink within the time duration T, such that the amount of flow reaching the sink is maximized. The problem is NP-complete. We propose a pseudopolynomial algorithm which can optimally solve the problem.