{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:36Z","timestamp":1740109416164,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T00:00:00Z","timestamp":1494806400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["822-10"],"award-info":[{"award-number":["822-10"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161\/2011"],"award-info":[{"award-number":["1161\/2011"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1841\/14"],"award-info":[{"award-number":["1841\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-017-9776-7","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T03:12:23Z","timestamp":1494817943000},"page":"987-1010","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Minimum-Cost Flows in Unit-Capacity Networks"],"prefix":"10.1007","volume":"61","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagi","family":"Hed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,15]]},"reference":[{"key":"9776_CR1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01585705","volume":"53","author":"RK Ahuja","year":"1992","unstructured":"Ahuja, R.K., Goldberg, A.V., Orlin, J.B., Tarjan, R.E.: Finding Minimum-Cost Flows by Double Scaling. Math. Prog. 53, 243\u2013266 (1992)","journal-title":"Math. Prog."},{"key":"9776_CR2","first-page":"211","volume-title":"Optimization. Handbooks in operations research and management science, vol. 1","author":"RK Ahuja","year":"1989","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. In: Nemhauser, G.L., Rinnooy Kan, A.H.G., Todd, M.J. (eds.) Optimization. Handbooks in operations research and management science, vol. 1, pp. 211\u2013369. North-Holland, Amsterdam (1989)"},{"key":"9776_CR3","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall (1993)"},{"key":"9776_CR4","doi-asserted-by":"crossref","unstructured":"Bertsekas, D.P.: Distributed asynchronous relaxation methods for linear network flow problems. Technical Report LIDS-p-1986, Lab. for decision systems M.I.T. (1986)","DOI":"10.1109\/CDC.1986.267433"},{"key":"9776_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01586039","volume":"54","author":"RG Bland","year":"1992","unstructured":"Bland, R.G., Jensen, D.L.: On the computational behavior of a polynomial-time network flow algorithm. Math. Prog. 54, 1\u201341 (1992)","journal-title":"Math. Prog."},{"key":"9776_CR6","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1137\/S0097539796313490","volume":"28","author":"BV Cherkassky","year":"1999","unstructured":"Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28, 1326\u20131346 (1999)","journal-title":"SIAM J. Comput."},{"key":"9776_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Sankowski, P., Vladu, A.: Negative-weight shortest paths and unit capacity minimum cost flow in \u00d5 (m 10\/7 w) time. In: SODA, pp. 752\u2013771 (2017)","DOI":"10.1137\/1.9781611974782.48"},{"key":"9776_CR8","doi-asserted-by":"crossref","unstructured":"Daitch, S.I., Spielman, D.A.: Faster approximate lossy generalized flow via interior point algorithms. In: STOC, pp. 451\u2013460 (2008)","DOI":"10.1145\/1374376.1374441"},{"key":"9776_CR9","unstructured":"Duan, R., Pettie, S., Su, H.: Scaling algorithms for approximate and exact maximum weight matching. CoRR, arXiv: 1112.0790 (2011)"},{"key":"9776_CR10","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4, 507\u2013518 (1975)","journal-title":"SIAM J. Comput."},{"key":"9776_CR11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach. 34, 596\u2013615 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9776_CR12","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N.: Scaling algorithms for network problems. J. Comp. Sys. Sci. 31, 148\u2013168 (1985)","journal-title":"J. Comp. Sys. Sci."},{"key":"9776_CR13","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"HN Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster Scaling Algorithms for Network Problems. SIAM J. Comput. 18, 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"key":"9776_CR14","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"AV Goldberg","year":"1995","unstructured":"Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM J. Comput. 24, 494\u2013504 (1995)","journal-title":"SIAM J. Comput."},{"key":"9776_CR15","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/S0895480194281185","volume":"10","author":"AV Goldberg","year":"1997","unstructured":"Goldberg, A.V., Kennedy, R.: Global Price Updates Help. SIAM J. Disc. Math. 10, 551\u2013572 (1997)","journal-title":"SIAM J. Disc. Math."},{"key":"9776_CR16","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","volume":"15","author":"AV Goldberg","year":"1990","unstructured":"Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Oper. Res. 15, 430\u2013466 (1990)","journal-title":"Math. Oper. Res."},{"key":"9776_CR17","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2, Algorithm for Maximum Matching in Bipartite Graphs. SIAM J. Comput. 2, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"9776_CR18","unstructured":"Karzanov, A.V.: O nakhozhdenii maksimal?nogo potoka v setyakh spetsial?nogo vida i nekotorykh prilozheniyakh. In: Matematicheskie Voprosy Upravleniya Proizvodstvom, volume 5. Moscow State University Press, Moscow, 1973. In Russian; title translation: On Finding Maximum Flows in Networks with Special Structure and Some Applications"},{"key":"9776_CR19","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York (1976)"},{"key":"9776_CR20","doi-asserted-by":"crossref","unstructured":"Madry, A.: Navigating central path with electrical flows: From flows to matchings, and back. In: FOCS, pp. 253\u2013262 (2013)","DOI":"10.1109\/FOCS.2013.35"},{"key":"9776_CR21","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"JB Orlin","year":"1993","unstructured":"Orlin, J.B.: Faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41, 338\u2013350 (1993)","journal-title":"Oper. Res."},{"key":"9776_CR22","doi-asserted-by":"crossref","unstructured":"Ramshaw, L., Tarjan, R.: Endre a weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs. In: FOCS, pp. 581\u2013590 (2012)","DOI":"10.1109\/FOCS.2012.9"},{"key":"9776_CR23","first-page":"181","volume-title":"Discrete structures and algorithms","author":"H R\u00f6ck","year":"1980","unstructured":"R\u00f6ck, H.: Scaling techniques for minimal cost network flows. In: Pape, U. (ed.) Discrete structures and algorithms, pp. 181\u2013191. Carl Hansen, M\u00fcnich (1980)"},{"issue":"3","key":"9776_CR24","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: Strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247\u2013255 (1985)","journal-title":"Combinatorica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9776-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9776-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9776-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T13:02:23Z","timestamp":1569330143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9776-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,15]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9776"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9776-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,5,15]]}}}