{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T21:27:23Z","timestamp":1768512443347,"version":"3.49.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1985,9,1]],"date-time":"1985-09-01T00:00:00Z","timestamp":494380800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1985,9]]},"DOI":"10.1007\/bf02579369","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T18:19:33Z","timestamp":1174587573000},"page":"247-255","source":"Crossref","is-referenced-by-count":235,"title":["A strongly polynomial minimum cost circulation algorithm"],"prefix":"10.1007","volume":"5","author":[{"given":"\u00c9va","family":"Tardos","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579369_CR1","volume-title":"Research Report CORR 83\u201322","author":"R. P. Anstee","year":"1983","unstructured":"R. P. Anstee, A polynomial algorithm forb-matching: an alternative approach,Research Report CORR 83\u201322, University Waterloo, Waterloo, Ontario, 1983."},{"key":"BF02579369_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1287\/moor.10.2.251","volume":"10","author":"W. H. Cunningham","year":"1985","unstructured":"W. H. Cunningham andA. Frank, A primal dual algorithm for submodular flows;Mathematics of Operations Research,10 (1985), 251\u2013262.","journal-title":"Mathematics of Operations Research"},{"key":"BF02579369_CR3","first-page":"1277","volume":"11","author":"E. A. Dinits","year":"1970","unstructured":"E. A. Dinits, Algorithm for solution of a problem of maximum flow in a network with power estimation;Soviet Math. Dokl.,11 (1970), 1277\u20131280.","journal-title":"Soviet Math. Dokl."},{"key":"BF02579369_CR4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Systems of distinct representatives and linear algebra;J. Res. Nat. Bur. Standards,71 B (1967), 241\u2013245.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF02579369_CR5","first-page":"67","volume-title":"Combinatorial Structures and Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, Submodular functions, matroids and certain polyhedra, in:Combinatorial Structures and Applications, (R. K. Guy et al. eds.) 1970 Gordon and Breach, New York 67\u201387."},{"key":"BF02579369_CR6","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"J. Edmonds","year":"1977","unstructured":"J. Edmonds andR. Giles, A min-max relation for submodular functions on graphs,Annals of Discrete Math. 1 (1977), 185\u2013204.","journal-title":"Annals of Discrete Math."},{"key":"BF02579369_CR7","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds andR. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems,J. ACM 19 (1972), 248\u2013264.","journal-title":"J. ACM"},{"key":"BF02579369_CR8","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, jr. andD. R. Fulkerson,Flows in Networks, Princeton University Press, Princeton N. J., 1962."},{"key":"BF02579369_CR9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1137\/0109002","volume":"9","author":"D. R. Fulkerson","year":"1961","unstructured":"D. R. Fulkerson, An Out-of-Kilter method for minimal cost flow problems,J. Soc. Indust. Appl. Math. 9 (1961), 18\u201327.","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"BF02579369_CR10","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, jr. andL. Lov\u00e1sz, Factoring polynomials with rational coefficients,Math. Ann. 261 (1982), 515\u2013534.","journal-title":"Math. Ann."},{"key":"BF02579369_CR11","first-page":"368","volume":"17","author":"C. L. Lucchesi","year":"1978","unstructured":"C. L. Lucchesi andD. H. Younger, A minimax theorem for directed graphs,J. London Math. Soc. 17 (1978), 368\u2013374.","journal-title":"J. London Math. Soc."},{"key":"BF02579369_CR12","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N. Megiddo","year":"1981","unstructured":"N. Megiddo, Towards a genuinely polynomial algorithm for linear programming,SIAM J. Comput. 12 (1981), 347\u2013353.","journal-title":"SIAM J. Comput."},{"key":"BF02579369_CR13","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1098\/rspa.1960.0144","volume":"257","author":"G. J. Minty","year":"1960","unstructured":"G. J. Minty, Monotone Networks,Proc. Roy. Soc. London, Ser. A,257 (1960), 194\u2013212.","journal-title":"Proc. Roy. Soc. London, Ser. A"},{"key":"BF02579369_CR14","first-page":"181","volume-title":"Discrete Structures and Algorithms","author":"H. R\u00f6ck","year":"1980","unstructured":"H. R\u00f6ck, Scaling techniques for minimal cost network flows, in:Discrete Structures and Algorithms, (U. Page ed.) 1980, Carl Hanser, M\u00fcnchen, 181\u2013191."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579369.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579369\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T12:45:03Z","timestamp":1558183503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,9]]}},"alternative-id":["BF02579369"],"URL":"https:\/\/doi.org\/10.1007\/bf02579369","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,9]]}}}