{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:59Z","timestamp":1740122459497,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"JSPS KAKENHI","award":["19H04068","20H05794"],"award-info":[{"award-number":["19H04068","20H05794"]}]},{"name":"JSPS KAKENHI","award":["22K11910","23H03349"],"award-info":[{"award-number":["22K11910","23H03349"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s10878-024-01199-7","type":"journal-article","created":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T19:02:12Z","timestamp":1724698932000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights"],"prefix":"10.1007","volume":"48","author":[{"given":"Tetsuya","family":"Fujie","sequence":"first","affiliation":[]},{"given":"Yuya","family":"Higashikawa","sequence":"additional","affiliation":[]},{"given":"Naoki","family":"Katoh","sequence":"additional","affiliation":[]},{"given":"Junichi","family":"Teruyama","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2114-1917","authenticated-orcid":false,"given":"Yuki","family":"Tokuni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,26]]},"reference":[{"issue":"2","key":"1199_CR1","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","volume":"52","author":"PK Agarwal","year":"1989","unstructured":"Agarwal PK, Sharir M, Shor P (1989) Sharp upper and lower bounds on the length of general davenport-Schinzel sequences. J Comb Theory Ser A 52(2):228\u2013274","journal-title":"J Comb Theory Ser A"},{"key":"1199_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup S, Gavoille C, Kaplan H, Rauhe T (2002) Nearest common ancestors: a survey and a new distributed algorithm. In: Proceedings of the 14th annual ACM symposium on Parallel algorithms and architectures (SPAA 2002), pp 258\u2013264","DOI":"10.1145\/564870.564914"},{"issue":"9","key":"1199_CR3","doi-asserted-by":"publisher","first-page":"3534","DOI":"10.1007\/s00453-019-00589-2","volume":"81","author":"GP Arumugam","year":"2019","unstructured":"Arumugam GP, Augustine J, Golin MJ, Srikanthan P (2019) Minmax regret k-sink location on a dynamic path network with uniform capacities. Algorithmica 81(9):3534\u20133585","journal-title":"Algorithmica"},{"key":"1199_CR4","unstructured":"Belmonte R, Higashikawa Y, Katoh N, Okamoto Y (2015) Polynomial-time approximability of the k-sink location problem. CoRR arXiv:1503.02835"},{"key":"1199_CR5","doi-asserted-by":"crossref","unstructured":"Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN 2000), pp 88\u201394","DOI":"10.1007\/10719839_9"},{"key":"1199_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: Proceedings of the 29th international workshop on combinatorial algorithms (IWOCA 2018), pp 78\u201389","DOI":"10.1007\/978-3-319-94667-2_7"},{"key":"1199_CR7","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1016\/j.tcs.2019.05.047","volume":"806","author":"R Benkoczi","year":"2020","unstructured":"Benkoczi R, Bhattacharya B, Higashikawa Y, Kameda T, Katoh N (2020) Minsum $$k$$-sink problem on path networks. Theor Comput Sci 806:388\u2013401","journal-title":"Theor Comput Sci"},{"key":"1199_CR8","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 path and tree networks. Theor Comput Sci 607:411\u2013425","journal-title":"Theor Comput Sci"},{"key":"1199_CR9","doi-asserted-by":"crossref","unstructured":"Bhattacharya B, Golin MJ, Higashikawa Y, Kameda T, Katoh N (2017) Improved algorithms for computing k-sink on dynamic flow path networks. In: Proceedings of the 15th workshop on algorithms and data structures (WADS 2017), pp 133\u2013144","DOI":"10.1007\/978-3-319-62127-2_12"},{"key":"1199_CR10","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: Proceedings of the 29th international symposium on algorithms and computation (ISAAC 2018)"},{"key":"1199_CR11","unstructured":"Chen D, Golin MJ (2016) Sink evacuation on trees with dynamic confluent flows. In: 27th international symposium on algorithms and computation (ISAAC 2016)"},{"issue":"7","key":"1199_CR12","doi-asserted-by":"publisher","first-page":"1948","DOI":"10.1007\/s00453-022-01083-y","volume":"85","author":"D Chen","year":"2023","unstructured":"Chen D, Golin MJ (2023) Minmax centered $$k$$-partitioning of trees and applications to sink evacuation with dynamic confluent flows. Algorithmica 85(7):1948\u20132000","journal-title":"Algorithmica"},{"issue":"3","key":"1199_CR13","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1287\/opre.6.3.419","volume":"6","author":"LR Ford","year":"1958","unstructured":"Ford LR, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Oper Res 6(3):419\u2013433","journal-title":"Oper Res"},{"key":"1199_CR14","first-page":"52","volume-title":"Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights","author":"T Fujie","year":"2021","unstructured":"Fujie T, Higashikawa Y, Katoh N, Teruyama J, Tokuni Y (2021) Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights. Algorithms and Computation, WALCOM, pp 52\u201364"},{"key":"1199_CR15","unstructured":"Golin MJ, Sandeep S (2018) Minmax-regret $$k$$-sink location on a dynamic tree network with uniform capacities. CoRR arXiv:1806.03814"},{"key":"1199_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2022.02.027","volume":"315","author":"MJ Golin","year":"2022","unstructured":"Golin MJ, Sandeep S (2022) Minmax regret for sink location on dynamic flow paths with general capacities. Discrete Appl Math 315:1\u201326","journal-title":"Discrete Appl Math"},{"issue":"2","key":"1199_CR17","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S Hart","year":"1986","unstructured":"Hart S, Sharir M (1986) Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2):151\u2013177","journal-title":"Combinatorica"},{"issue":"4","key":"1199_CR18","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J Hershberger","year":"1989","unstructured":"Hershberger J (1989) Finding the upper envelope of $$n$$ line segments in $${O}(n \\log n)$$ time. Inf Process Lett 33(4):169\u2013174","journal-title":"Inf Process Lett"},{"key":"1199_CR19","unstructured":"Higashikawa Y (2014) Studies on the space exploration and the sink location under incomplete information towards applications to evacuation planning. Ph.D. thesis, Kyoto University, Japan"},{"issue":"4","key":"1199_CR20","doi-asserted-by":"publisher","first-page":"539","DOI":"10.7155\/jgaa.00336","volume":"18","author":"Y Higashikawa","year":"2014","unstructured":"Higashikawa Y, Golin MJ, Katoh N (2014) Minimax regret sink location problem in dynamic tree networks with uniform capacity. J Graph Algorithms Appl 18(4):539\u2013555","journal-title":"J Graph Algorithms Appl"},{"key":"1199_CR21","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 SW, Golin MJ, Katoh N, Ni G, Su B, Xu Y (2015) Minimax regret 1-sink location problem in dynamic path networks. Theor Comput Sci 588:24\u201336","journal-title":"Theor Comput Sci"},{"key":"1199_CR22","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 MJ, Katoh N (2015) Multiple sink location problems in dynamic path networks. Theor Comput Sci 607:2\u201315","journal-title":"Theor Comput Sci"},{"issue":"6","key":"1199_CR23","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 SW, Kameda T, Katoh N, Saburi S (2018) Minimax regret 1-median problem in dynamic path networks. Theory Comput Syst 62(6):1392\u20131408","journal-title":"Theory Comput Syst"},{"issue":"1","key":"1199_CR24","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 E (2000) The quickest transshipment problem. Math Oper Res 25(1):36\u201362","journal-title":"Math Oper Res"},{"key":"1199_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust discrete optimization and its applications","author":"P Kouvelis","year":"1997","unstructured":"Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, London"},{"issue":"2","key":"1199_CR26","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.ejor.2015.09.022","volume":"250","author":"H Li","year":"2016","unstructured":"Li H, Xu Y (2016) Minimax regret 1-sink location problem with accessibility in dynamic general networks. Eur J Oper Res 250(2):360\u2013366","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1199_CR27","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10878-014-9716-2","volume":"31","author":"H Li","year":"2016","unstructured":"Li H, Xu Y, Ni G (2016) Minimax regret vertex 2-sink location problem in dynamic path networks. J Comb Optim 31(1):79\u201394","journal-title":"J Comb Optim"},{"key":"1199_CR28","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 a sink location problem in dynamic tree networks. Discrete Appl Math 154:2387\u20132401","journal-title":"Discrete Appl Math"},{"key":"1199_CR29","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/1008861.1008872","volume":"12","author":"A Porto","year":"1980","unstructured":"Porto A, Matos A (1980) Ackermann and the superpowers. ACM SIGACT News 12:90\u201395. https:\/\/doi.org\/10.1145\/1008861.1008872","journal-title":"ACM SIGACT News"},{"key":"1199_CR30","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-540-76796-1_21","volume-title":"Research trends in combinatorial optimization","author":"M Skutella","year":"2009","unstructured":"Skutella M (2009) An introduction to network flows over time. Research trends in combinatorial optimization. Springer, Berlin, pp 451\u2013482"},{"issue":"2","key":"1199_CR31","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/(SICI)1520-6750(199903)46:2<147::AID-NAV2>3.0.CO;2-4","volume":"46","author":"GL Vairaktarakis","year":"1999","unstructured":"Vairaktarakis GL, Kouvelis P (1999) Incorporation dynamic aspects and uncertainty in 1-median location problems. Naval Res Log (NRL) 46(2):147\u2013168","journal-title":"Naval Res Log (NRL)"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01199-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01199-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01199-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T20:53:13Z","timestamp":1727297593000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01199-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,26]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1199"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01199-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,8,26]]},"assertion":[{"value":"13 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"15"}}