License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.25
URN: urn:nbn:de:0030-drops-67951
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6795/
Go to the corresponding LIPIcs Volume Portal

Chen, Di ; Golin, Mordecai

Sink Evacuation on Trees with Dynamic Confluent Flows

pdf-format:
LIPIcs-ISAAC-2016-25.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2016:6795,
  author =	{Di Chen and Mordecai Golin},
  title =	{{Sink Evacuation on Trees with Dynamic Confluent Flows}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6795},
  URN =		{urn:nbn:de:0030-drops-67951},
  doi =		{10.4230/LIPIcs.ISAAC.2016.25},
  annote =	{Keywords: Sink Evacuation, Dynamic Flow, Facility Location, Parametric Search}
}

Keywords: Sink Evacuation, Dynamic Flow, Facility Location, Parametric Search
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI