MPI-INF Logo
Publications

Thesis (Server    domino.mpi-inf.mpg.de)

Thesis

Master's thesis | @MastersThesis{RaufDiss04, ... | Masterarbeit

Rauf, Imran

Earliest Arrival Flows with Multiple Sources

Universität des Saarlandes, March, 2005

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.

Combinatorial Optimization, Network Flows
Public
Download File(s):
Raimund Seidel
Martin Skutella
Completed
9
March
2005
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@MASTERSTHESIS{RaufDiss04,
AUTHOR = {Rauf, Imran},
TITLE = {Earliest Arrival Flows with Multiple Sources},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2005},
TYPE = {Master's thesis}
MONTH = {March},
}





Entry last modified by Christine Kiesel, 05/01/2005
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer
Created
03/15/2005 04:07:49 PM
Revision
1.
0.


Editor
Christine Kiesel
Ulrich Meyer


Edit Date
01.05.2005 18:39:28
03/15/2005 04:07:49 PM