{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T20:55:41Z","timestamp":1762030541911,"version":"3.40.4"},"reference-count":21,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T00:00:00Z","timestamp":1740355200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP24K14825"],"award-info":[{"award-number":["JP24K14825"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>A dynamic network is a directed graph where an arc has a capacity and a transit time. A dynamic flow is a flow defined in a dynamic network. We consider the problem of finding a minimum\u2010cost dynamic flow in a dynamic network where an arc has a cost. It is known that this problem is NP\u2010hard. Klinz and Woeginger asked whether the minimum\u2010cost dynamic flow problem in a fixed graph (i.e., a graph is given a priori, and it is not a part of the input) can be solved in polynomial time. We prove that if the cost of each arc is non\u2010negative, the capacity of each arc is an integer, and the target flow value is a constant integer, then this problem can be solved in polynomial time.<\/jats:p>","DOI":"10.1002\/net.22272","type":"journal-article","created":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T18:37:26Z","timestamp":1740508646000},"page":"437-444","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Minimum\u2010Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow Value"],"prefix":"10.1002","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-2730","authenticated-orcid":false,"given":"Naoyuki","family":"Kamiyama","sequence":"first","affiliation":[{"name":"Institute of Mathematics for Industry Kyushu University  Fukuoka Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,2,24]]},"reference":[{"volume-title":"Network Flows \u2010 Theory, Algorithms and Applications","year":"1993","author":"Ahuja R. K.","key":"e_1_2_7_2_1"},{"volume-title":"Flows in Networks","year":"1962","author":"Ford Jr L. R.","key":"e_1_2_7_3_1"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316888568"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.3.419"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76796-1_21"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.1.36.15211"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.52"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.5"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.004"},{"key":"e_1_2_7_11_1","unstructured":"M.Schl\u00f6ter \u201cFlows Over Time and Submodular Function Minimization \u201d2018.PhD thesis Technische Universit\u00e4t Berlin."},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01415527"},{"key":"e_1_2_7_13_1","first-page":"1343","volume-title":"Proceedings of the 26th Annual ACM\u2010SIAM Symposium on Discrete Algorithms","author":"Lin M.","year":"2015"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21726"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10112"},{"key":"e_1_2_7_16_1","unstructured":"M.Schl\u00f6terandR.Weismantel \u201cMinimum\u2010cost flows over time \u201d2022.Technical Report arXiv:2206.00526 arXiv."},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427215"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_7_19_1","series-title":"Wiley\u2010Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1986"},{"volume-title":"Algorithms and Combinatorics","year":"2003","author":"Schrijver A.","key":"e_1_2_7_20_1"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.536364"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22272","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T12:21:55Z","timestamp":1746188515000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.22272"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,24]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.1002\/net.22272"],"URL":"https:\/\/doi.org\/10.1002\/net.22272","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[2025,2,24]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}