{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T05:50:48Z","timestamp":1760853048685},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2004,12,29]],"date-time":"2004-12-29T00:00:00Z","timestamp":1104278400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2005,5]]},"DOI":"10.1007\/s10107-004-0562-3","type":"journal-article","created":{"date-parts":[[2004,12,29]],"date-time":"2004-12-29T05:34:13Z","timestamp":1104298453000},"page":"181-202","source":"Crossref","is-referenced-by-count":12,"title":["A capacity scaling algorithm for M-convex submodular flow"],"prefix":"10.1007","volume":"103","author":[{"given":"Satoru","family":"Iwata","sequence":"first","affiliation":[]},{"given":"Satoko","family":"Moriguchi","sequence":"additional","affiliation":[]},{"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,12,29]]},"reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1287\/mnsc.49.7.950.16384","volume":"49","author":"Ahuja","year":"2003","unstructured":"Ahuja, R.K., Hochbaum, D.S., Orlin, J.B.: Solving the convex cost integer dual network flow problem. Manage. Sci. 49, 950?964 (2003)","journal-title":"Manage. Sci."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1287\/moor.10.2.251","volume":"10","author":"Cunningham","year":"1985","unstructured":"Cunningham, W.H., Frank, A.: A primal-dual algorithm for submodular flows. Math. Oper. Res. 10, 251?262 (1985)","journal-title":"Math. Oper. Res."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"Dress","year":"1992","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math. 93, 214?250 (1992)","journal-title":"Adv. Math."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"Edmonds","year":"1977","unstructured":"Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185?204 (1977)","journal-title":"Ann. Discrete Math."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248?264 (1972)","journal-title":"J. ACM"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s101070100253","volume":"92","author":"Fleischer","year":"2002","unstructured":"Fleischer, L., Iwata, S., McCormick, S.T.: A faster capacity scaling algorithm for minimum cost submodular flow. Math. Program. Ser. A 92, 119?139 (2002)","journal-title":"Math. Program. Ser. A"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0095-8956(84)90029-7","volume":"36","author":"Frank","year":"1984","unstructured":"Frank, A.: Finding feasible vectors of Edmonds-Giles polyhedra. J. Comb. Theory, Ser. B 36, 221?239 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"CR8","first-page":"189","volume":"21","author":"Fujishige","year":"1978","unstructured":"Fujishige, S.: Algorithms for solving the independent flow-problems. J. Oper. Res. Soc. Japan 21, 189?204 (1978)","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"CR9","unstructured":"Fujishige, S.: Submodular Functions and Optimization. North-Holland, Amsterdam 1991"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF03167272","volume":"9","author":"Fujishige","year":"1992","unstructured":"Fujishige, S., Zhang, X.: New algorithms for the intersection problem of submodular systems. Japan J. Indust. Appl. Math. 9, 369?382 (1992)","journal-title":"Japan J. Indust. Appl. Math."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1287\/moor.19.2.390","volume":"19","author":"Hochbaum","year":"1994","unstructured":"Hochbaum, D.S.: Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Math. Oper. Res. 19, 390?409 (1994)","journal-title":"Math. Oper. Res."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48, 686?701 (2001)","journal-title":"J. ACM"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1137\/S0895480100369584","volume":"16","author":"Hochbaum","year":"2003","unstructured":"Hochbaum, D.S., Queyranne, M.: Minimizing a convex cost closure set. SIAM J. Discrete Math. 16, 192?207 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"CR14","first-page":"299","volume":"76","author":"Iwata","year":"1997","unstructured":"Iwata, S.: A capacity scaling algorithm for convex cost submodular flows. Math. Program. 76, 299?308 (1997)","journal-title":"Math. Program."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/S0097539701397813","volume":"32","author":"Iwata","year":"2003","unstructured":"Iwata, S.: A faster scaling algorithm for minimizing submodular functions. SIAM J. Comput. 32, 833?840 (2003)","journal-title":"SIAM J. Comput."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 761?777 (2001)","journal-title":"J. ACM"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Iwata, S., McCormick, S.T., Shigeno, M.: A strongly polynomial cut canceling algorithm for the submodular flow problem. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds), Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 1610, pp. 259?272 Springer-Verlag 1999","DOI":"10.1007\/3-540-48777-8_20"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1137\/S1052623499352012","volume":"13","author":"Iwata","year":"2003","unstructured":"Iwata, S., Shigeno, M.: Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization. SIAM J. Optim. 13, 204?211 (2003)","journal-title":"SIAM J. Optim."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Gr\u00f6tschel, M., Korte, B. (eds), Mathematical Programming ?- The State of the Art, pp. 235?257 Springer-Verlag 1983","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1080\/1055678031000099178","volume":"18","author":"Moriguchi","year":"2003","unstructured":"Moriguchi, S., Murota, K.: Capacity scaling algorithm for scalable M-convex submodular flow problems. Optim. Methods Softw. 18, 207?218 (2003)","journal-title":"Optim. Methods Softw."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, I: optimality criteria. SIAM J. Discrete Math. 9, 545?561 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, II: algorithms. SIAM J. Discrete Math. 9, 562?576 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1006\/aima.1996.0084","volume":"124","author":"Murota","year":"1996","unstructured":"Murota, K.: Convexity and Steinitz?s exchange property. Adv. Math. 124, 272?311 (1996)","journal-title":"Adv. Math."},{"key":"CR24","first-page":"313","volume":"83","author":"Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Program. 83, 313?371 (1998)","journal-title":"Math. Program."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s004930050047","volume":"19","author":"Murota","year":"1999","unstructured":"Murota, K.: Submodular flow problem with a nonseparable cost function. Combinatorica 19, 87?109 (1999)","journal-title":"Combinatorica"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia 2003","DOI":"10.1137\/1.9780898718508"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF03167422","volume":"20","author":"Murota","year":"2003","unstructured":"Murota, K., Tamura, A.: Application of M-convex submodular flow problem to mathematical economics. Japan J. Indust. Appl. Math. 20, 257?277 (2003)","journal-title":"Japan J. Indust. Appl. Math."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B 80, 346?355 (2000)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0166-218X(03)00255-5","volume":"134","author":"Shioura","year":"2003","unstructured":"Shioura, A.: Fast scaling algorithms for M-convex function minimization with application to resource allocation problem. Discrete Appl. Math. 134, 303?316 (2003)","journal-title":"Discrete Appl. Math."},{"key":"CR30","unstructured":"Tamura, A.: Coordinatewise domain scaling algorithm for M-convex function minimization. Math. Program., to appear"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1287\/moor.11.2.362","volume":"11","author":"Tardos","year":"1986","unstructured":"Tardos, \u00c9., Tovey, C.A., Trick, M.A.: Layered augmenting path algorithms. Math. Oper. Res. 11, 362?370 (1986)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0562-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-004-0562-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0562-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:49:57Z","timestamp":1559123397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-004-0562-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,29]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["562"],"URL":"https:\/\/doi.org\/10.1007\/s10107-004-0562-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12,29]]}}}