Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14401
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBaumann, Nadine
dc.contributor.authorSkutella, Martin
dc.date.accessioned2021-12-17T10:07:41Z-
dc.date.available2021-12-17T10:07:41Z-
dc.date.issued2008
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15628-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14401-
dc.description.abstractEarliest arrival flows capture the essence of evacuation planning. 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 for many years. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.en
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othernetwork flowen
dc.subject.otherflow over timeen
dc.subject.otherearliest arrival flowen
dc.subject.otherevacuation problemen
dc.titleEarliest Arrival Flows with Multiple Sourcesen
dc.typeResearch Paperen
tub.accessrights.dnbfreeen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2008, 35en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
dc.type.versionsubmittedVersionen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-035-2008.pdf
Format: Adobe PDF | Size: 322.55 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.