{"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":1740122459576,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"SPS KAKENHI","award":["19H04068"],"award-info":[{"award-number":["19H04068"]}]},{"name":"JSPS KAKENHI","award":["20H05794","22K11910"],"award-info":[{"award-number":["20H05794","22K11910"]}]},{"name":"JSPS KAKENHI","award":["23H03349"],"award-info":[{"award-number":["23H03349"]}]},{"name":"the preparation for the establishment of university fellowships towards the creation of science technology innovation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s10878-024-01213-y","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:07:29Z","timestamp":1728302849000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Faster algorithms for evacuation problems in networks with a single sink of small degree and bounded capacitated edges"],"prefix":"10.1007","volume":"48","author":[{"given":"Yuya","family":"Higashikawa","sequence":"first","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,10,7]]},"reference":[{"key":"1213_CR1","first-page":"369","volume":"27","author":"EJ Anderson","year":"1994","unstructured":"Anderson EJ, Philpott AB (1994) Optimisation of flows in networks over time. Probab, Stat Optim 27:369\u2013382","journal-title":"Probab, Stat Optim"},{"issue":"1","key":"1213_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Quart Appl Math 16(1):87\u201390","journal-title":"Quart Appl Math"},{"key":"1213_CR3","doi-asserted-by":"crossref","unstructured":"Busacker RG, Gowen PJ (1960) A procedure for determining a family of minimum-cost network flow patterns. Operations Research Office, ORO-TP-15","DOI":"10.21236\/AD0249662"},{"issue":"7","key":"1213_CR4","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 M (2023) Minmax centered k-partitioning of trees and applications to sink evacuation with dynamic confluent flows. Algorithmica 85(7):1948\u20132000","journal-title":"Algorithmica"},{"key":"1213_CR5","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":"3","key":"1213_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"WH Cunningham","year":"1985","unstructured":"Cunningham WH (1985) On submodular function minimization. Combinatorica 5(3):185\u2013192","journal-title":"Combinatorica"},{"key":"1213_CR7","doi-asserted-by":"crossref","unstructured":"Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. In: Combinatorial Optimization\u2014Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5\u20139, 2001 Revised Papers, Springer, pp 11\u201326","DOI":"10.1007\/3-540-36478-1_2"},{"issue":"3\u20135","key":"1213_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0167-6377(98)00037-6","volume":"23","author":"L Fleischer","year":"1998","unstructured":"Fleischer L, Tardos \u00c9 (1998) Efficient continuous-time dynamic network flow algorithms. Oper Res Lett 23(3\u20135):71\u201380","journal-title":"Oper Res Lett"},{"key":"1213_CR9","doi-asserted-by":"crossref","unstructured":"Ford L, Fulkerson D (1962) Flows in networks princeton univ. Press Princeton","DOI":"10.1515\/9781400875184"},{"key":"1213_CR10","unstructured":"Ford LR (1956) Network flow theory"},{"issue":"4","key":"1213_CR11","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"},{"issue":"1","key":"1213_CR12","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"},{"issue":"1","key":"1213_CR13","first-page":"2","volume":"3","author":"M Iri","year":"1960","unstructured":"Iri M (1960) A new method of solving transportation-network problems. J Oper Res Soc Jpn 3(1):2","journal-title":"J Oper Res Soc Jpn"},{"key":"1213_CR14","first-page":"633","volume":"6","author":"WS Jewell","year":"1958","unstructured":"Jewell WS (1958) Optimal flow through networks. Oper Res 6:633\u2013633","journal-title":"Oper Res"},{"key":"1213_CR15","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1016\/j.tcs.2019.08.004","volume":"795","author":"N Kamiyama","year":"2019","unstructured":"Kamiyama N (2019) Discrete newton methods for the evacuation problem. Theoret Comput Sci 795:510\u2013519","journal-title":"Theoret Comput Sci"},{"key":"1213_CR16","doi-asserted-by":"crossref","unstructured":"Kamiyama N, Katoh N, Takizawa A (2006) An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity. IEICE Transactions 89-D(8):2372\u20132379","DOI":"10.1093\/ietisy\/e89-d.8.2372"},{"issue":"17","key":"1213_CR17","doi-asserted-by":"publisher","first-page":"3665","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. Discret Appl Math 157(17):3665\u20133677","journal-title":"Discret Appl Math"},{"issue":"16","key":"1213_CR18","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 dynamic tree networks. Discret Appl Math 154(16):2387\u20132401","journal-title":"Discret Appl Math"},{"key":"1213_CR19","unstructured":"Moore EF (1959) The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, pp 285\u2013292"},{"key":"1213_CR20","doi-asserted-by":"crossref","unstructured":"Orlin J (1988) A faster strongly polynomial minimum cost flow algorithm. In: Proceedings of the Twentieth annual ACM symposium on Theory of Computing, pp 377\u2013387","DOI":"10.1145\/62212.62249"},{"issue":"2","key":"1213_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1002\/net.21726","volume":"69","author":"M Saho","year":"2017","unstructured":"Saho M, Shigeno M (2017) Cancel-and-tighten algorithm for quickest flow problems. Networks 69(2):179\u2013188","journal-title":"Networks"},{"key":"1213_CR22","unstructured":"Schl\u00f6ter M (2018) Flows over time and submodular function minimization. Technische Universitaet Berlin (Germany)"},{"key":"1213_CR23","doi-asserted-by":"crossref","unstructured":"Schl\u00f6ter M, Skutella M (2017) Fast and memory-efficient algorithms for evacuation problems. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 821\u2013840","DOI":"10.1137\/1.9781611974782.52"},{"key":"1213_CR24","doi-asserted-by":"crossref","unstructured":"Schl\u00f6ter M, Skutella M, Van\u00a0Tran K (2022) A faster algorithm for quickest transshipments via an extended discrete newton method. In: Proceedings of the 2022 Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp 90\u2013102","DOI":"10.1137\/1.9781611977073.5"},{"key":"1213_CR25","doi-asserted-by":"crossref","unstructured":"Thorup M (2003) Integer priority queues with decrease key in constant time and the single source shortest paths problem. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp 149\u2013158","DOI":"10.1145\/780542.780566"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01213-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01213-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01213-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T19:09:35Z","timestamp":1729192175000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01213-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1213"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01213-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"22 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 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":"18"}}