×

Improved algorithms for computing \(k\)-sink on dynamic flow path networks. (English) Zbl 1493.68261

Ellen, Faith (ed.) et al., Algorithms and data structures. 15th international symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10389, 133-144 (2017).
Summary: We address the problem of locating \(k\) sinks on dynamic flow path networks with \(n\) vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in \(O(n\log n + k^2\log ^4 n)\) and \(O(n\log ^3 n)\) time, respectively. When all edges have the same capacity, we also present two algorithms which run in \(O(n + k^2\log ^2n)\) time and \(O(n\log n)\) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities \(O(kn\log ^2n)\) [G. P. Arumugam et al., “A polynomial time algorithm for minimax-regret evacuation on a dynamic path”, Preprint, arXiv:1404.5448] and \(O(kn)\) [Y. Higashikawa et al., Theor. Comput. Sci. 607, Part 1, 2–15 (2015; Zbl 1332.68079)], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/merging them in an efficient manner.
For the entire collection see [Zbl 1369.68023].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms
90B10 Deterministic network models in operations research
90B80 Discrete location and assignment

Citations:

Zbl 1332.68079
PDFBibTeX XMLCite
Full Text: DOI arXiv