The maximum flow in dynamic networks

Abstract

The dynamic maximum flow problem that generalizes the static maximum flow problem is formulated and studied. We consider the problem on a network with capacities depending on time, fixed transit times on the arcs, and a given time horizon. The corresponding algorithm to solve this problem is proposed and some details concerning its complexity are discussed. Mathematics Subject Classification 2000: 90B10, 90C35, 90C27.