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)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview 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)