{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T16:18:33Z","timestamp":1743265113276,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054350","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["Recent developments in maximum flow algorithms"],"prefix":"10.1007","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"1_CR1","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993."},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1287\/opre.37.5.748","volume":"37","author":"R. K. Ahuja","year":"1989","unstructured":"R. K. Ahuja and J. B. Orlin. A Fast and Simple Algorithm for the Maximum Flow Problem. Oper. Res., 37:748\u2013759, 1989.","journal-title":"Oper. Res."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1137\/0218065","volume":"18","author":"R. K. Ahuja","year":"1989","unstructured":"R. K. Ahuja, J. B. Orlin, and R. E. Tarjan. Improved Time Bounds for the Maximum Flow Problem. SIAM J. Comput., 18:939\u2013954, 1989.","journal-title":"SIAM J. Comput."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(90)90024-R","volume":"35","author":"N. Alon","year":"1990","unstructured":"N. Alon. Generating Pseudo-Random Permutations and Maximum Flow Algorithms. Information Processing Let., 35:201\u2013204, 1990.","journal-title":"Information Processing Let."},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"R. J. Anderson and J. C. Setubal. Goldberg's Algorithm for the Maximum Flow in Perspective: a Computational Study. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 1\u201318. AMS, 1993.","DOI":"10.1090\/dimacs\/012\/01"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"A. A. Bencz\u00dar and D. R. Karger. Approximating s-t Minimum Cuts in \u00d5(n 2) Time. In Proc. 28th Annual ACM Symposium on Theory of Computing, pages 47\u201356, 1996.","DOI":"10.1145\/237814.237827"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/S0097539791221529","volume":"24","author":"J. Cheriyan","year":"1995","unstructured":"J. Cheriyan and T. Hagerup. A randomized maximum flow algorithm. SIAM Journal on Computing, 24:203\u2013226, 1995.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1_CR8","first-page":"144","volume":"25","author":"J. Cheriyan","year":"1996","unstructured":"J. Cheriyan, T. Hagerup, and K. Mehlhorn. An o(n 3)-time Maximum Flow Algorithm. SIAM J. Comput., 25:1144\u20131170, 1996.","journal-title":"SIAM J. Comput."},{"key":"1_CR9","first-page":"112","volume":"7","author":"B. V. Cherkassky","year":"1977","unstructured":"B. V. Cherkassky. Algorithm for Construction of Maximal Flows in Networks with Complexity of OV 2\u221aE) Operations. Mathematical Methods of Solution of Economical Problems, 7:112\u2013125, 1977. (In Russian).","journal-title":"Mathematical Methods of Solution of Economical Problems"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"B. V. Cherkassky","year":"1997","unstructured":"B. V. Cherkassky and A. V. Goldberg. On Implementing Push-Relabel Method for the Maximum Flow Problem. Algorithmica, 19:390\u2013410, 1997.","journal-title":"Algorithmica"},{"key":"1_CR11","first-page":"359","volume-title":"Activity Analysis and Production and Allocation","author":"G. B. Dantzig","year":"1951","unstructured":"G. B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T. C. Koopmans, editor, Activity Analysis and Production and Allocation, pages 359\u2013373. Wiley, New York, 1951."},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF01415937","volume":"33","author":"U. Derigs","year":"1989","unstructured":"U. Derigs and W. Meier. Implementing Goldberg's Max-Flow Algorithm \u2014 A Computational Investigation. ZOR \u2014 Methods and Models of Operations Research, 33:383\u2013403, 1989.","journal-title":"ZOR \u2014 Methods and Models of Operations Research"},{"key":"1_CR13","first-page":"1277","volume":"11","author":"E. A. Dinic","year":"1970","unstructured":"E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl., 11:1277\u20131280, 1970.","journal-title":"Soviet Math. Dokl."},{"key":"1_CR14","volume-title":"Issledovaniya po Diskretnoi Matematike","author":"E. A. Dinic","year":"1973","unstructured":"E. A. Dinic. Metod porazryadnogo sokrashcheniya nevyazok i transportnye zadachi. In Issledovaniya po Diskretnoi Matematike. Nauka, Moskva, 1973. In Russian. Title translation: Excess Scaling and Transportation Problems."},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. Assoc. Comput. Mach., 19:248\u2013264, 1972.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"S. Even and R. E. Tarjan. Network Flow and Testing Graph Connectivity. SIAM J. Comput, 4:507\u2013518, 1975.","journal-title":"SIAM J. Comput"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L. R. Ford Jr.","year":"1956","unstructured":"L. R. Ford, Jr. and D. R. Fulkerson. Maximal Flow Through a Network. Canadian Journal of Math., 8:399\u2013404, 1956.","journal-title":"Canadian Journal of Math."},{"key":"1_CR18","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow. Scaling Algorithms for Network Problems. J. of Comp. and Sys. Sci., 31:148\u2013168, 1985.","journal-title":"J. of Comp. and Sys. Sci."},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0022-0000(80)90035-5","volume":"21","author":"Z. Galil","year":"1980","unstructured":"Z. Galil and A. Naamad. An O(EV log2 V) Algorithm for the Maximal Flow Problem. J. Comput. System Sci., 21:203\u2013217, 1980.","journal-title":"J. Comput. System Sci."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Z. Galil and X. Yu. Short Length Version of Menger's Theorem. In Proc. 27th Annual ACM Symposium on Theory of Computing, pages 499\u2013508, 1995.","DOI":"10.1145\/225058.225267"},{"key":"1_CR22","unstructured":"A. V. Goldberg. A New Max-Flow Algorithm. Technical Report MIT\/LCS\/TM-291, Laboratory for Computer Science, M.I.T., 1985."},{"key":"1_CR23","unstructured":"A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, M.I.T., January 1987. (Also available as Technical Report TR-374, Lab. for Computer Science, M.I.T., 1987)."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and S. Rao. Beyond the Flow Decomposition Barrier. In Proc. 38th IEEE Annual Symposium on Foundations of Computer Science, pages 2\u201311, 1997.","DOI":"10.1109\/SFCS.1997.646087"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and S. Rao. Flows in Undirected Unit Capacity Networks. In Proc. 38th IEEE Annual Symposium on Foundations of Computer Science, pages 32\u201335, 1997.","DOI":"10.1109\/SFCS.1997.646090"},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A. V. Goldberg","year":"1988","unstructured":"A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921\u2013940, 1988.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","volume":"15","author":"A. V. Goldberg","year":"1990","unstructured":"A. V. Goldberg and R. E. Tarjan. Finding Minimum-Cost Circulations by Successive Approximation. Math. of Oper. Res., 15:430\u2013466, 1990.","journal-title":"Math. of Oper. Res."},{"key":"1_CR28","unstructured":"D. R. Karger. Global Min-Cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. In Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993."},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"D. R. Karger. Minimum Cuts in Near-Linear Time. In Proc. 28th Annual ACM Symposium on Theory of Computing, pages 56\u201363, 1996.","DOI":"10.1145\/237814.237829"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"D. R. Karger. Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. In Proc. 29th Annual ACM Symposium on Theory of Computing, pages 240\u2013249, 1997.","DOI":"10.1145\/258533.258596"},{"key":"1_CR31","unstructured":"D. R. Karger. Better Random Sampling Algorithms for Flows in Undirected Graphs. In Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pages 490\u2013499, 1998."},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"D. R. Karger and M. Levine. Finding Maximum Flows in Undirected Graphs Seems Easier than Bipratire Matching. In Proc. 30th Annual ACM Symposium on Theory of Computing, 1997.","DOI":"10.1145\/276698.276714"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"D. R. Karger and C. Stein. A New Approach to the Minimum Cut Problem. J. Assoc. Comput. Mach., 43, 1996.","DOI":"10.1145\/234533.234534"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"D.R. Karger. Random Sampling in Cut, Flow, and Network Design Problems. In Proc. 26th Annual ACM Symposium on Theory of Computing, pages 648\u2013657, 1994. Submitted to Math. of Oper. Res.","DOI":"10.1145\/195058.195422"},{"key":"1_CR35","volume-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom, volume 5","author":"A. V. Karzanov","year":"1973","unstructured":"A. V. Karzanov. 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":"1_CR36","first-page":"434","volume":"15","author":"A. V. Karzanov","year":"1974","unstructured":"A. V. Karzanov. Determining the Maximal Flow in a Network by the Method of Preflows. Soviet Math. Dok., 15:434\u2013437, 1974.","journal-title":"Soviet Math. Dok."},{"key":"1_CR37","unstructured":"V. King, S. Rao, and R. Tarjan. A Faster Deterministic Maximum Flow Algorithm. In Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 157\u2013164, 1992."},{"key":"1_CR38","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1006\/jagm.1994.1044","volume":"17","author":"V. King","year":"1994","unstructured":"V. King, S. Rao, and R. Tarjan. A Faster Deterministic Maximum Flow Algorithm. J. Algorithms, 17:447\u2013474, 1994.","journal-title":"J. Algorithms"},{"key":"1_CR39","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, NY., 1976."},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki. A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph. Algorithmica, 7:583\u2013596, 1992.","journal-title":"Algorithmica"},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki. Computing Edge-Connectivity in Multigraphs and Capacitated Graphs. SIAM J. Disc. Math., 5:54\u201366, 1992.","journal-title":"SIAM J. Disc. Math."},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Q. C. Nguyen and V. Venkateswaran. Implementations of Goldberg-Tarjan Maximum Flow Algorithm. In D. S. Johnson and C. C. McGeoch, editors, Network Flows and Matching: First DIMACS Implementation Challenge, pages 19\u201342. AMS, 1993.","DOI":"10.1090\/dimacs\/012\/02"},{"key":"1_CR43","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"J. B. Orlin","year":"1993","unstructured":"J. B. Orlin. A Faster Strongly Polynomial Minimum Cost Flow Algorithm. Oper. Res., 41:338\u2013350, 1993.","journal-title":"Oper. Res."},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"S. Phillips and J. Westbrook. Online Load Balancing and Network Flow. In Proc. 25th Annual ACM Symposium on Theory of Computing, pages 402\u2013411, 1993.","DOI":"10.1145\/167088.167201"},{"key":"1_CR45","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230050405","volume":"5","author":"J. C. Picard","year":"1975","unstructured":"J. C. Picard and H. D. Ratliff. Minimum Cuts and Related Problems. Networks, 5:357\u2013370, 1975.","journal-title":"Networks"},{"key":"1_CR46","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan. A Data Structure for Dynamic Trees. J. Comput. System Sci., 26:362\u2013391, 1983.","journal-title":"J. Comput. System Sci."},{"key":"1_CR47","volume-title":"Technical report","author":"C. Wallacher","year":"1991","unstructured":"C. Wallacher. A Generalization of the Minimum-Mean Cycle Selection Rule in Cycle Canceling Algorithms. Technical report, Preprints in Optimization, Institute f\u00fcr Angewandte Mathematik, Technische Universit\u00c4t Braunschweig, Germany, 1991."},{"key":"1_CR48","volume-title":"Technical report","author":"C. Wallacher","year":"1991","unstructured":"C. Wallacher and U. Zimmermann. A Combinatorial Interior Point Method for Network Flow Problems. Technical report, Preprints in Optimization, Institute f\u00fcr Angewandte Mathematik, Technische Universit\u00c4t Braunschweig, Germany, 1991."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:20:42Z","timestamp":1736407242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054350"}},"subtitle":["Invited lecture"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/bfb0054350","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}