1 Search Results for "Baumann, Nadine"

Document

Computing earliest arrival flows with multiple sources

Authors: Nadine Baumann and Martin Skutella

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

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.

Cite as

Nadine Baumann and Martin Skutella. Computing earliest arrival flows with multiple sources. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.4},
  URN =		{urn:nbn:de:0030-drops-5672},
  doi =		{10.4230/DagSemProc.05361.4},
  annote =	{Keywords: Networks, flows over time, dynamic flows, earliest arrival, evacuation}
}

Refine by Author
1 Baumann, Nadine
1 Skutella, Martin

Refine by Classification

Refine by Keyword
1 Networks
1 dynamic flows
1 earliest arrival
1 evacuation
1 flows over time

Refine by Type
1 document

Refine by Publication Year
1 2006

1 Search Results for "Baumann, Nadine"

Computing earliest arrival flows with multiple sources

Abstract

Cite as

Thanks for your feedback!

Could not send message