{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:28:58Z","timestamp":1787239738595,"version":"3.56.0"},"reference-count":70,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Rev."],"published-print":{"date-parts":[[1991,6]]},"abstract":"<jats:p>The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity concerning the algorithmic aspects of network flow problems over the past few years has been particularly striking. Several techniques have proven to be very successful in permitting researchers to make these recent contributions: (i) scaling of the problem data; (ii) improved analysis of algorithms, especially amortized worst-case performance and the use of potential functions; and (iii) enhanced data structures. This survey illustrates some of these techniques and their usefulness in developing faster network flow algorithms. The discussion focuses on the design of faster algorithms from the worst-case perspective, and is limited to the following fundamental problems: the shortest path problem, the maximum flow problem, and the minimum cost flow problem. Several representative algorithms from each problem class are considered, including the radix heap algorithm for the shortest path problem, preflow push algorithms for the maximum flow problem, and the pseudoflow push algorithms for the minimum cost flow problem.<\/jats:p>","DOI":"10.1137\/1033048","type":"journal-article","created":{"date-parts":[[2005,3,7]],"date-time":"2005-03-07T02:21:47Z","timestamp":1110162107000},"page":"175-219","source":"Crossref","is-referenced-by-count":32,"title":["Some Recent Advances in Network Flows"],"prefix":"10.1137","volume":"33","author":[{"given":"Ravindra K.","family":"Ahuja","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas L.","family":"Magnanti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James B.","family":"Orlin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,18]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585705"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(89)01005-4"},{"key":"R4","unstructured":"R. K. Ahuja, T. L. Magnanti, J. B. Orlin,  Network Flows : Theory, Algorithms, and Applications, [forthcoming]"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77615"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.5.748"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.1.S5"},{"key":"R8","unstructured":"Ravindra K. Ahuja, James B. Orlin,  Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems,  1987, Working Paper 1908-87, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA; Naval Res. Log., 1991, to appear"},{"key":"R9","unstructured":"R. K. Ahuja, J. B. Orlin, M. R. Reddy,  Applications of network flow problems,  1990, work in progress"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0218065"},{"key":"R11","unstructured":"F. Barahona, E. Tardos,  Note on Weintraub's minimum cost flow algorithm, Research Report, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA.,  1987"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/opre.20.3.619"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"R14","unstructured":"D. P. Bertsekas,  A distributed algorithm for the assignment problem, Working Paper, Laboratory for Information Decision Systems, Massachusetts Institute of Technology, Cambridge, MA.,  1979"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. P. Bertsekas,  Distributed relaxation methods for linear network flow problems,  Proc. 25th IEEE Conference on Decision and Control, Athens, Greece, 1986","DOI":"10.1109\/CDC.1986.267433"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589405"},{"key":"R17","unstructured":"R. G. Bland, D. L. Jensen,  On the computational behavior of a polynomial-time network flow algorithm, Tech. Report, 661, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.,  1985"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. G. Busaker, P. J. Gowen,  A procedure for determining a family of minimal-cost network flow patterns, O.R.O. Tech. Report, 15, Operational Research Office, The Johns Hopkins University, Baltimore, MD,  1961","DOI":"10.21236\/AD0249662"},{"key":"R19","unstructured":"J. Cheriyan, T. Hagerup,  A randomized algorithm for maximum network flow,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science,  1989"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0218072"},{"key":"R21","first-page":"112","volume":"7","author":"Cherkasky R. V.","year":"1977","journal-title":"Math. Methods Solution Econom. Probl."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.2.187"},{"key":"R23","series-title":"Annals of Mathematics Studies, no. 38","first-page":"215","volume-title":"Linear inequalities and related systems","author":"Dantzig G. B.","year":"1956"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.1.161"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363610"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R27","first-page":"1277","volume":"11","author":"Dinic E. A.","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056816"},{"key":"R30","volume-title":"Graph algorithms","author":"Even Shimon","year":"1979"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90137-4"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.32.3.341"},{"key":"R33","unstructured":"L. R. Ford, Jr.,  Network flow theory, Report, P-923, Rand Corporation, Santa Monica, CA.,  1956"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"R35","volume-title":"Flows in networks","author":"Ford, Jr. L. R.","year":"1962"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.11.7.724"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580882"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264254"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90035-5"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Z. Galil, E. tardos,  An  O(n2(m+nlogn)logn) min-cost flow algorithm,  Proc. 27th Annual IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society, Washington, D.C.,  1986,  136\u2013146","DOI":"10.1109\/SFCS.1986.7"},{"key":"R43","unstructured":"A. V. Goldberg,  A new max-flow algorithm, Tech. Report, MIT\/LCS\/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA.,  1985"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, E. Tardos, R. E. Tarjan,  Network flow algorithms, Tech. Report, Department of Computer Science, Stanford University, Stanford, CA.,  1989","DOI":"10.21236\/ADA214689"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, R. E. Tarjan,  A new approach to the maximum flow problem,  Proc. 18th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York,  1986,  136\u2013146","DOI":"10.1145\/12130.12144"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, R. E. Tarjan,  Solving minimum cost flow problem by successive approximation,  Proc. 19th Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York,  1987,  7\u201318, Full version: Math. Oper. Res., 15, pp. 430\u2013466","DOI":"10.1145\/28395.28397"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"R49","unstructured":"D. B. Johnson,  Efficient special purpose priority queues,  Proc. 15th Annual Allerton Conference on Comm., Control and Computing,  1977b"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786986"},{"key":"R51","first-page":"434","volume":"15","author":"Karzanov A. V.","year":"1974","journal-title":"Soviet Math. Dokl."},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.3.205"},{"key":"R53","volume-title":"Combinatorial optimization: networks and matroids","author":"Lawler Eugene L.","year":"1976"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90016-9"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"R56","first-page":"285","volume-title":"Proc. Internat. Sympos. Switching Theory 1957, Part II","author":"Moore Edward F.","year":"1959"},{"key":"R57","unstructured":"J. B. Orlin,  Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem, Tech. Report, 1615-84, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA.,  1984"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585517"},{"key":"R60","first-page":"181","volume-title":"Discrete structures and algorithms (Proc. Conf., Berlin, 1979)","author":"Rock Hans","year":"1980"},{"key":"R61","unstructured":"Y. Shiloach,  An  O(nIlog2(I)) maximum flow algorithm, Tech. Report, STAN-CS-78-702, Computer Science Department, Stanford University, Stanford, CA.,  1978"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90076-2"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1960.32"},{"key":"R69","first-page":"347","volume":"7","author":"Williams J. W. J.","year":"1964","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"R70","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1975.59"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1033048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:48:35Z","timestamp":1787237315000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/1033048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":70,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["10.1137\/1033048"],"URL":"https:\/\/doi.org\/10.1137\/1033048","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}