A Labeling Algorithm for the Earliest and Latest Time-Varying Maximum Flow Problems

摘要

The time-varying maximum flow problem is to find the maximum flow in a time-varying network. A time-varying network is the network which the transit time and the capacity of an arc are functions of the departure time at the beginning node of an arc. The earliest (or the latest) maximum flow is the maximum flow could be sent from the source node to the sink node in the time-varying network within the given time duration with the earliest (or the latest) arrival time. We assume that the transit time and the capacity of an arc are positive integers, and waiting at any node is prohibited except the source node. The problem is known to be NP-complete. A labeling algorithms is proposed for solving problems in pseudo polynomial time.