Campus Event Calendar
Event Entry
What and Who
Earliest-Arrival Flows with Multiple Sources
Imran Rauf
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 9 June 2005
13:00
-- Not specified --
45
016
Saarbrücken
Abstract
This talk 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$.
We present the first exact algorithm that solves a class of the
earliest arrival flow problems 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.
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$.
We present the first exact algorithm that solves a class of the
earliest arrival flow problems 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.
Contact
--email hidden
passcode not visible
logged in users only
Bahareh Kadkhodazadeh, 05/31/2005 13:02
Bahareh Kadkhodazadeh, 04/07/2005 15:45 -- Created document.
Bahareh Kadkhodazadeh, 04/07/2005 15:45 -- Created document.