Bhattacharya, Binay; Golin, Mordecai J.; Higashikawa, Yuya; Kameda, Tsunehiko; Katoh, Naoki 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]. Cited in 8 Documents 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 \textit{B. Bhattacharya} et al., Lect. Notes Comput. Sci. 10389, 133--144 (2017; Zbl 1493.68261) Full Text: DOI arXiv