License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2021.13
URN: urn:nbn:de:0030-drops-148825
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14882/
Go to the corresponding OASIcs Volume Portal

Benkoczi, Robert ; Bhattacharya, Binay ; Higashikawa, Yuya ; Kameda, Tsunehiko ; Katoh, Naoki ; Teruyama, Junichi

Locating Evacuation Centers Optimally in Path and Cycle Networks

pdf-format:
OASIcs-ATMOS-2021-13.pdf (1 MB)

Abstract

We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).

BibTeX - Entry

@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
  author =	{Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
  title =	{{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{13:1--13:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14882},
  URN =		{urn:nbn:de:0030-drops-148825},
  doi =		{10.4230/OASIcs.ATMOS.2021.13},
  annote =	{Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}

Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network
Collection: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Issue Date: 2021
Date of publication: 27.09.2021

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