License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05361.4
URN: urn:nbn:de:0030-drops-5672
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/567/
Go to the corresponding Portal |
Baumann, Nadine ;
Skutella, Martin
Computing earliest arrival flows with multiple sources
Abstract
Earliest arrival flows are motivated by applications related to
evacuation. Given a network with capacities and transit times on
the arcs, a subset of source nodes with supplies and a sink node,
the task is to send the given supplies from the sources to the sink
"as quickly as possible". The latter requirement is made more
precise by the earliest arrival property which requires that the
total amount of flow that has arrived at the sink is maximal for all
points in time simultaneously.
It is a classical result from the 1970s that, for the special case
of a single source node, earliest arrival flows do exist and can be
computed by essentially applying the Successive Shortest Path
Algorithm for min-cost flow computations. While it has previously
been observed that an earliest arrival flow still exists for
multiple sources, the problem of computing one efficiently has been
open. We present an exact algorithm for this problem whose running
time is strongly polynomial in the input plus output size of the
problem.
BibTeX - Entry
@InProceedings{baumann_et_al:DagSemProc.05361.4,
author = {Baumann, Nadine and Skutella, Martin},
title = {{Computing earliest arrival flows with multiple sources}},
booktitle = {Algorithmic Aspects of Large and Complex Networks},
pages = {1--3},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {5361},
editor = {Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/567},
URN = {urn:nbn:de:0030-drops-5672},
doi = {10.4230/DagSemProc.05361.4},
annote = {Keywords: Networks, flows over time, dynamic flows, earliest arrival, evacuation}
}
Keywords: |
|
Networks, flows over time, dynamic flows, earliest arrival, evacuation |
Collection: |
|
05361 - Algorithmic Aspects of Large and Complex Networks |
Issue Date: |
|
2006 |
Date of publication: |
|
08.05.2006 |