Abstract
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)\) [1] and O(kn) [11], 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.
B. Bhattacharya — Partially supported by a Discovery Grant from NSERC of Canada
M.J. Golin — Partially supported by Hong Kong RGC GRF grant 16208415
Y. Higashikawa and N. Katoh — Supported by JSPS KAKENHI Grant-in-Aid for Young Scientists (B) (17K12641)
Y. Higashikawa — Supported by JST CREST (JPMJCR1402)
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Arumugam, G.P., Augustine, J., Golin, M.J., Srikanthan, P.: A polynomial time algorithm for minimax-regret evacuation on a dynamic path (2014). arXiv:1404,5448v1
Benkoczi, R., Bhattacharya, B., Chrobak, M., Larmore, L.L., Rytter, W.: Faster algorithms for k-medians in trees. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 218–227. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45138-9_16
Bhattacharya, B., Kameda, T.: Improved algorithms for computing minmax regret sinks on path and tree networks. Theoretical Computer Science 607, 411–425 (2015)
Cheng, S.-W., Higashikawa, Y., Katoh, N., Ni, G., Su, B., Xu, Y.: Minimax regret 1-sink location problems in dynamic path networks. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 121–132. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38236-9_12
Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Operations research 6(3), 419–433 (1958)
Frederickson, G.N.: Optimal algorithms for tree partitioning. In: Proc. 2nd ACM-SIAM Symp. Discrete Algorithms, pp. 168–177 (1991)
Frederickson, G.N., Johnson, D.B.: Finding \(k\)th paths and \(p\)-centers by generating and searching good data structures. J. Algorithms 4, 61–80 (1983)
Hamacher, H.W., Tjandra, S.A.: Mathematical modeling of evacuation problems: a state of the art. In: Pedestrian and Evacuation Dynamics, pp. 227–266. Springer Verlag (2002)
Higashikawa, Y.: Studies on the space exploration and the sink location under incomplete information towards applications to evacuation planning. PhD thesis, Kyoto University, Japan (2014)
Higashikawa, Y., Golin, M.J., Katoh, N.: Minimax regret sink location problem in dynamic tree networks with uniform capacity. J. of Graph Algorithms and Applications 18(4), 539–555 (2014)
Higashikawa, Y., Golin, M. J., Katoh, N.: Multiple sink location problems in dynamic path networks. Theoretical Computer Science 607, 2–15 (2015)
Hoppe, B., Tardos, É.: The quickest transshipment problem. Mathematics of Operations Research 25(1), 36–62 (2000)
Kamiyama, N., Katoh, N., Takizawa, A.: An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity. IEICE Transactions 89-D(8), 2372–2379 (2006)
Mamada, S., Makino, K., Fujishige, S.: Optimal sink location problem for dynamic flows in a tree network. IEICE Trans. Fundamentals E85-A, 1020–1025 (2002)
Mamada, S., Uno, T., Makino, K., Fujishige, S.: An \({O}(n\log ^2 n)\) algorithm for a sink location problem in dynamic tree networks. Discrete Applied Mathematics 154, 2387–2401 (2006)
Megiddo, N.: Combinatorial optimization with rational objective functions. Math. Oper. Res. 4, 414–424 (1979)
Megiddo, N., Tamir, A.: New results on the complexity of \(p\)-center problems. SIAM J. Comput. 12, 751–758 (1983)
Skutella, M.: An introduction to network flows over time. In: Research Trends in Combinatorial Optimization, pp. 451–482. Springer (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Bhattacharya, B., Golin, M.J., Higashikawa, Y., Kameda, T., Katoh, N. (2017). Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)