{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:37Z","timestamp":1777596157839,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JSPS KAKENHI Grant-in-Aid for Scientific Research","award":["JP19H04068"],"award-info":[{"award-number":["JP19H04068"]}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K12641"],"award-info":[{"award-number":["JP17K12641"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Rev Socionetwork Strat"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s12626-019-00047-z","type":"journal-article","created":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T02:04:11Z","timestamp":1567562651000},"page":"163-208","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Survey on Facility Location Problems in Dynamic Flow Networks"],"prefix":"10.1007","volume":"13","author":[{"given":"Yuya","family":"Higashikawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naoki","family":"Katoh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,4]]},"reference":[{"key":"47_CR1","unstructured":"http:\/\/www.mlit.go.jp\/river\/mlit_at_wcdrr\/pdf\/Forum2_en.pdf"},{"key":"47_CR2","volume-title":"Network flows: theory, algorithms, and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: theory, algorithms, and applications. Upper Saddle River: Prentice Hall."},{"key":"47_CR3","unstructured":"Arumugam, G. P., Augustine, J., Golin, M. J., & Srikanthan, P. (2014). A polynomial time algorithm for minimax-regret evacuation on a dynamic flow path. CoRR arXiv:1404.5448."},{"issue":"2","key":"47_CR4","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/S0377-2217(99)00257-X","volume":"123","author":"I Averbakh","year":"2000","unstructured":"Averbakh, I., & Berman, O. (2000). Algorithms for the \nrobust 1-center problem on a tree. European Journal of Operational Research, 123(2), 292\u2013302.","journal-title":"European Journal of Operational Research"},{"key":"47_CR5","unstructured":"Belmonte, R., Higashikawa, Y., Katoh, N., & Okamoto, Y. (2015). Polynomial-time approximability of the k-Sink Location problem. CoRR arXiv:1503.02835."},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Benkoczi, R., Bhattacharya, B., Higashikawa, Y., Kameda, T., & Katoh, N. (2018). Minsum k-sink problem on dynamic flow path networks. In Proc. the 29th international workshop on combinatorial algorithms (IWOCA 2018), LNCS 10979, pp. 78\u201389.","DOI":"10.1007\/978-3-319-94667-2_7"},{"key":"47_CR7","unstructured":"Benkoczi, R., Bhattacharya, B., Higashikawa, Y., Kameda, T., & Katoh, N. Minsum k-sink problem on path networks. Theoretical Computer Science\n                           (accepted)."},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Bhattacharya, B., Golin, M.\u00a0J., Higashikawa, Y., Kameda, T., & Katoh, N. (2017). Improved algorithms for computing k-sink on dynamic flow path networks. In Proc. the 15th algorithms and data structures symposium (WADS 2017), LNCS 10389, pp. 133\u2013144.","DOI":"10.1007\/978-3-319-62127-2_12"},{"key":"47_CR9","unstructured":"Bhattacharya, B., Higashikawa, Y., Kameda, T., & Katoh, N. (2018). An $$O(n^2\\log ^2 n)$$  time algorithm for minmax regret minsum sink on path networks. In Proc. the 29th international symposium on algorithms and computation (ISAAC 2018), LIPIcs 123, pp. 14:1\u201314:13."},{"key":"47_CR10","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/j.tcs.2015.07.009","volume":"607","author":"B Bhattacharya","year":"2015","unstructured":"Bhattacharya, B., & Kameda, T. (2015). Improved algorithms for computing minmax regret sinks on dynamic flow path and tree networks. Theoretical Computer Science, 607, 411\u2013425.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"47_CR11","first-page":"1","volume":"70","author":"B Bhattacharya","year":"2013","unstructured":"Bhattacharya, B., Kameda, T., & Song, Z. (2013). A linear time algorithm for computing minmax regret 1-median on a tree network. Algorithmica, 70(1), 1\u201320.","journal-title":"Algorithmica"},{"issue":"1","key":"47_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.orl.2007.02.012","volume":"36","author":"GS Brodal","year":"2008","unstructured":"Brodal, G. S., Georgiadis, L., & Katriel, I. (2008). An $$O(n \\log n)$$ version of the Averbakh-Berman algorithm for the robust median of a tree. Operations Research Letters, 36(1), 14\u201318.","journal-title":"Operations Research Letters"},{"issue":"1","key":"47_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01415527","volume":"37","author":"RE Burkard","year":"1993","unstructured":"Burkard, R. E., Dlaska, K., & Klinz, B. (1993). The quickest flow problem. Mathematical Methods of Operations Research, 37(1), 31\u201358.","journal-title":"Mathematical Methods of Operations Research"},{"key":"47_CR14","unstructured":"Chen, D., & Golin, M.\u00a0J. (2016). Sink evacuation on trees with dynamic confluent flows. In Proc. the 27th international symposium on algorithms and computation (ISAAC 2016), LIPIcs 64, pp. 25:1\u201325:13."},{"key":"47_CR15","unstructured":"Chen, D., & Golin, M.\u00a0J. (2018). Minmax centered k-partitioning of trees and applications to sink evacuation with dynamic confluent flows. CoRR arXiv:1803.09289."},{"issue":"1","key":"47_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., & Shmoys, D. B. (2002). A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1), 129\u2013149.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"47_CR17","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1002\/(SICI)1097-0037(199803)31:2<93::AID-NET4>3.0.CO;2-E","volume":"31","author":"B Chen","year":"1998","unstructured":"Chen, B., & Lin, C. (1998). Minmax-regret robust 1-median location on a tree. Networks, 31(2), 93\u2013103.","journal-title":"Networks"},{"key":"47_CR18","unstructured":"Cheng, S.\u00a0W., Higashikawa, Y., Katoh, N., Ni, G., Su, B., & Xu, Y. (2013). Minimax regret 1-sink location problems in a dynamic flow path network. In Proc. the 10th annual conference on theory and applications of models of computation (TAMC 2013), LNCS 7876, pp. 121\u2013132."},{"issue":"2","key":"47_CR19","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.orl.2007.05.009","volume":"36","author":"E Conde","year":"2008","unstructured":"Conde, E. (2008). A note on the minmax regret centdian location on trees. Operations Research Letters, 36(2), 271\u2013275.","journal-title":"Operations Research Letters"},{"key":"47_CR20","volume-title":"Network and discrete location: Models, algorithms, and applications","author":"MS Daskin","year":"2013","unstructured":"Daskin, M. S. (2013). Network and discrete location: Models, algorithms, and applications. Oxford: Wiley."},{"issue":"6","key":"47_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0167-6377(85)90002-1","volume":"3","author":"ME Dyer","year":"1985","unstructured":"Dyer, M. E., & Frieze, A. M. (1985). A simple heuristic for the p-center problem. Operations Research Letters, 3(6), 285\u2013288.","journal-title":"Operations Research Letters"},{"key":"47_CR22","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer."},{"key":"47_CR23","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1287\/opre.6.3.419","volume":"6","author":"LR Ford Jr","year":"1958","unstructured":"Ford, L. R, Jr., & Fulkerson, D. R. (1958). Constructing maximal dynamic flows from static flows. Operations Research, 6, 419\u2013433.","journal-title":"Operations Research"},{"key":"47_CR24","volume-title":"Flows in networks","author":"LR Ford Jr","year":"1962","unstructured":"Ford, L. R, Jr., & Fulkerson, D. R. (1962). Flows in networks. Princeton: Princeton University Press."},{"issue":"1","key":"47_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"GN Frederickson","year":"1983","unstructured":"Frederickson, G. N., & Johnson, D. B. (1983). Finding kth paths and p-centers by generating and searching good data structures. Journal of Algorithms, 4(1), 61\u201380.","journal-title":"Journal of Algorithms"},{"key":"47_CR26","unstructured":"Golin, M.\u00a0J., & Sandeep, S. (2018). Minmax-regret k-sink location on a dynamic flow tree network with uniform capacities. CoRR arXiv:1806.03814."},{"issue":"3","key":"47_CR27","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/j.tcs.2007.02.046","volume":"379","author":"A Hall","year":"2007","unstructured":"Hall, A., Hippler, S., & Skutella, M. (2007). Multicommodity flows over time: Efficient algorithms and complexity. Theoretical Computer Science, 379(3), 387\u2013404.","journal-title":"Theoretical Computer Science"},{"key":"47_CR28","unstructured":"Higashikawa, Y. (2014). Studies on the space exploration and the sink location under incomplete information towards applications to evacuation planning. Doctoral Dissertation accepted by Kyoto University."},{"key":"47_CR29","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.tcs.2014.02.010","volume":"588","author":"Y Higashikawa","year":"2015","unstructured":"Higashikawa, Y., Augustine, J., Cheng, S. W., Golin, M. J., Katoh, N., Ni, G., et al. (2015). Minimax regret 1-sink location problem in a dynamic flow path network. Theoretical Computer Science, 588, 24\u201336.","journal-title":"Theoretical Computer Science"},{"key":"47_CR30","unstructured":"Higashikawa, Y., Cheng, S.\u00a0W., Kameda, T., Katoh, N., & Saburi, S. (2016). Minimax regret 1-median problem in a dynamic flow path network. In Proc. the 27th international workshop on combinatorial algorithms (IWOCA 2016), LNCS 9843, pp. 122\u2013134."},{"issue":"6","key":"47_CR31","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1007\/s00224-017-9783-8","volume":"62","author":"Y Higashikawa","year":"2018","unstructured":"Higashikawa, Y., Cheng, S. W., Kameda, T., Katoh, N., & Saburi, S. (2018). Minimax regret 1-median problem in a dynamic flow path network. Theory of Computing Systems, 62(6), 1392\u20131408.","journal-title":"Theory of Computing Systems"},{"key":"47_CR32","unstructured":"Higashikawa, Y., Golin, M.\u00a0J., & Katoh, N. (2014). Minimax regret sink location problem in a dynamic flow tree network with uniform capacity. In Proc. the 8th international workshop on algorithms and computation (WALCOM 2014), LNCS 8344, pp. 125\u2013137."},{"key":"47_CR33","unstructured":"Higashikawa, Y., Golin, M.\u00a0J., & Katoh, N. (2014). Multiple sink location problems in a dynamic flow path network. In Proc. the 10th international conference on algorithmic aspects of information and management (AAIM 2014), LNCS 8546, pp. 149\u2013161."},{"issue":"4","key":"47_CR34","doi-asserted-by":"publisher","first-page":"539","DOI":"10.7155\/jgaa.00336","volume":"18","author":"Y Higashikawa","year":"2014","unstructured":"Higashikawa, Y., Golin, M. J., & Katoh, N. (2014). Minimax regret sink location problem in a dynamic flow tree network with uniform capacity. Journal of Graph Algorithms and Applications, 18(4), 539\u2013555.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"47_CR35","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2015.05.053","volume":"607","author":"Y Higashikawa","year":"2015","unstructured":"Higashikawa, Y., Golin, M. J., & Katoh, N. (2015). Multiple sink location problems in a dynamic flow path network. Theoretical Computer Science, 607, 2\u201315.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"47_CR36","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D. S., & Shmoys, D. B. (1985). A best possible approximation algorithm for the k-center problem. Mathematics of Operations Research, 10(2), 180\u2013184.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"47_CR37","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.25.1.36.15211","volume":"25","author":"B Hoppe","year":"2000","unstructured":"Hoppe, B., & Tardos, \u00c9. (2000). The quickest transshipment problem. Mathematics of Operations Research, 25(1), 36\u201362.","journal-title":"Mathematics of Operations Research"},{"key":"47_CR38","doi-asserted-by":"publisher","first-page":"2372","DOI":"10.1093\/ietisy\/e89-d.8.2372","volume":"89\u2013D(8)","author":"N Kamiyama","year":"2006","unstructured":"Kamiyama, N., Katoh, N., & Takizawa, A. (2006). An efficient algorithm for evacuation problem in dynamic flow network flows with uniform arc capacity. IEICE Transactions, 89\u2013D(8), 2372\u20132379.","journal-title":"IEICE Transactions"},{"issue":"17","key":"47_CR39","doi-asserted-by":"publisher","first-page":"3656","DOI":"10.1016\/j.dam.2009.04.007","volume":"157","author":"N Kamiyama","year":"2009","unstructured":"Kamiyama, N., Katoh, N., & Takizawa, A. (2009). An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths. Discrete Applied Mathematics, 157(17), 3656\u20133664.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"47_CR40","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0020-0190(75)90055-1","volume":"4","author":"ANC Kang","year":"1975","unstructured":"Kang, A. N. C., & Ault, D. A. (1975). Some properties of a centroid of a free tree. Information Processing Letters, 4(1), 18\u201320.","journal-title":"Information Processing Letters"},{"issue":"16","key":"47_CR41","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.1016\/j.dam.2006.04.010","volume":"154","author":"S Mamada","year":"2006","unstructured":"Mamada, S., Uno, T., Makino, K., & Fujishige, S. (2006). An $$O(n \\log ^2 n)$$ algorithm for the optimal sink location problem in a dynamic flow tree network. Discrete Applied Mathematics, 154(16), 2387\u20132401.","journal-title":"Discrete Applied Mathematics"},{"key":"47_CR42","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms. Oxford: Oxford University Press."},{"issue":"2","key":"47_CR43","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1998.0955","volume":"29","author":"B Schieber","year":"1998","unstructured":"Schieber, B. (1998). Computing a minimum weight k-link path in graphs with the concave monge property. Journal of Algorithms, 29(2), 204\u2013222.","journal-title":"Journal of Algorithms"},{"key":"47_CR44","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/978-3-642-45030-3_68","volume-title":"Algorithms and Computation","author":"Haitao Wang","year":"2013","unstructured":"Wang, H. Minmax regret 1-facility location on uncertain path networks. In Proc. the 24th international symposium on algorithms and computation (ISAAC 2013), pp. 733\u2013743."},{"issue":"3","key":"47_CR45","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1016\/j.ejor.2014.06.026","volume":"239","author":"H Wang","year":"2014","unstructured":"Wang, H. (2014). Minmax regret 1-facility location on uncertain path networks. European Journal of Operational Research, 239(3), 636\u2013643.","journal-title":"European Journal of Operational Research"}],"container-title":["The Review of Socionetwork Strategies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00047-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12626-019-00047-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00047-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T23:31:59Z","timestamp":1599089519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12626-019-00047-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,4]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s12626-019-00047-z","relation":{},"ISSN":["2523-3173","1867-3236"],"issn-type":[{"value":"2523-3173","type":"print"},{"value":"1867-3236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,4]]},"assertion":[{"value":"8 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}