Item

Abstract

This thesis addresses the earliest arrival flow problem, defined on dynamic networks with several sources and a single sink. A dynamic network is a directed graph with capacities and transit times on its edges. Given an integral supply specified at each source of a dynamic network, the problem is to send exactly the right amount of flow out of each source and into the sink, such that the amount of flow arriving at the sink by time $\theta$ is the maximum possible for all $\theta \geq 0$. One obvious approach is to solve the easier static flow problem in a time-expanded network that contains one copy of the same network for each discrete time step. However, this approach is not practical in general due to the exponential size of time-expanded networks. In \cite{FleischerSkutella}, Fleischer and Skutella describe a fully polynomial approximation scheme to solve this problem, while a special case when all transit times are zero, has been considered by Fleischer \cite{Fleischer01b}. This thesis presents the first exact algorithm that avoids a time-expanded network, and solves a more general class of the earliest arrival flow problem in dynamic networks with multiple sources. The class is characterized by the property that the total supply at the sources is equal to the value of the maximum dynamic flow in time bound $T$, where $T$ is the minimum time needed to evacuate all supplies.