max planck institut
informatik

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

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

## Thesis - Master's thesis | @MastersThesis | Masterarbeit

Author(s)*: Rauf, Imran RaufDiss04 English

Title*: Earliest Arrival Flows with Multiple Sources Universität des Saarlandes Master's thesis March 2005

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. Combinatorial Optimization, Network Flows Public View attachments here:thesis.ps.gz

1. Referee: Raimund Seidel Martin Skutella Completed 9 March 2005

MPG Unit: 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},
}

Attachment Section

View attachments here: