Locating Evacuation Centers Optimally in Path and Cycle Networks

Medientyp: Sonstige Veröffentlichung; Elektronischer Konferenzbericht; E-Artikel

Titel: Locating Evacuation Centers Optimally in Path and Cycle Networks

Beteiligte: Benkoczi, Robert [VerfasserIn]; Bhattacharya, Binay [VerfasserIn]; Higashikawa, Yuya [VerfasserIn]; Kameda, Tsunehiko [VerfasserIn]; Katoh, Naoki [VerfasserIn]; Teruyama, Junichi [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021

Sprache: Englisch

DOI: https://doi.org/10.4230/OASIcs.ATMOS.2021.13

Schlagwörter: facility location ; minmax sink ; Efficient algorithms ; dynamic flow in network ; evacuation problem

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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).

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: