2026-07-21T23:52:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6795 2024-03-06T10:38:54Z ddc:004 open_access

Sink Evacuation on Trees with Dynamic Confluent Flows Chen, Di Golin, Mordecai Sink Evacuation Dynamic Flow Facility Location Parametric Search Let G = (V, E) be a graph modelling a building or road network in which edges have-both travel times (lengths) and capacities associated with them. An edge’s capacity is the number of people that can enter that edge in a unit of time. In emergencies, people evacuate towards the exits. If too many people try to evacuate through the same edge, congestion builds up and slows down the evacuation. Graphs with both lengths and capacities are known as Dynamic Flow networks. An evacuation plan for G consists of a choice of exit locations and a partition of the people at the vertices into groups, with each group evacuating to the same exit. The evacuation time of a plan is the time it takes until the last person evacuates. The k-sink evacuation problem is to provide an evacuation plan with k exit locations that minimizes the evacuation time. It is known that this problem is NP-Hard for general graphs but no polynomial time algorithm was previously known even for the case of G a tree. This paper presents an O(nk^2 log^5 n) algorithm for the k-sink evacuation problem on trees, which can also be applied to a more general class of problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Di Chen and Mordecai Golin 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.25 urn:nbn:de:0030-drops-67951 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.25 eng https://creativecommons.org/licenses/by/3.0/legalcode