Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Rauf, Imran

MPI-INF D1 Publications
Show all entries of:this year (2020)last year (2019)two years ago (2018)Open in Notes
Action:login to update

Thesis - Master's thesis | @MastersThesis | Masterarbeit

Author(s)*:Rauf, Imran
BibTeX citekey*:RaufDiss04

Title, School
Title*:Earliest Arrival Flows with Multiple Sources
School:Universität des Saarlandes
Type of Thesis*:Master's thesis

Note, Abstract, Copyright
LaTeX 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.

Keywords:Combinatorial Optimization, Network Flows
Download Access Level:Public
Download File(s):View attachments here:

Referees, Status, Dates
1. Referee:Raimund Seidel
Supervisor:Martin Skutella
Date Kolloquium:9 March 2005

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

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

Hide details for Attachment SectionAttachment Section

View attachments here:

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)

Ulrich Meyer
03/15/2005 04:07:49 PM

Christine Kiesel
Ulrich Meyer

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