{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:39:53Z","timestamp":1760708393471},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540594086"},{"type":"electronic","value":"9783540492450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59408-6_49","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:15:17Z","timestamp":1330276517000},"page":"157-171","source":"Crossref","is-referenced-by-count":41,"title":["On implementing push-relabel method for the maximum flow problem"],"prefix":"10.1007","author":[{"given":"Boris V.","family":"Cherkassky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","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":"13_CR2","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":"13_CR3","doi-asserted-by":"crossref","unstructured":"J. Cheriyan, T. Hagerup, and K. Mehlhorn. Can a Maximum Flow be Computed in o(nm) Time? In Proc. ICALP, 1990.","DOI":"10.1007\/BFb0032035"},{"key":"13_CR4","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1137\/0218072","volume":"18","author":"J. Cheriyan","year":"1989","unstructured":"J. Cheriyan and S. N. Maheshwari. Analysis of Preflow Push Algorithms for Maximum Netwrok Flow. SIAM J. Comput., 18:1057\u20131086, 1989.","journal-title":"SIAM J. Comput."},{"key":"13_CR5","first-page":"90","volume-title":"Collected Papers, Issue 3: Combinatorial Methods for Flow Problems","author":"B. V. Cherkassky","year":"1979","unstructured":"B. V. Cherkassky. A Fast Algorithm for Computing Maximum Flow in a Network. In A. V. Karzanov, editor, Collected Papers, Issue 3: Combinatorial Methods for Flow Problems, pages 90\u201396. The Institute for Systems Studies, Moscow, 1979. In Russian. English translation appears in AMS Trans., Vol. 158, pp. 23\u201330, 1994."},{"key":"13_CR6","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":"13_CR7","volume-title":"Linear Programming and Extensions","author":"G. B. Dantzig","year":"1962","unstructured":"G. B. Dantzig. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962."},{"key":"13_CR8","doi-asserted-by":"crossref","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":"13_CR9","doi-asserted-by":"crossref","unstructured":"U. Derigs and W. Meier. An Evaluation of Algorithmic Refinements and Proper Data-Structures for the Preflow-Push Approach for Maximum Flow. In ASI Series on Computer and System Sciences, volume 8, pages 209\u2013223. NATO, 1992.","DOI":"10.1007\/978-3-642-77489-8_3"},{"key":"13_CR10","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":"13_CR11","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":"13_CR12","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":"13_CR13","unstructured":"A. V. Goldberg. A New Max-Flow Algorithm. Technical Report MIT\/LCS\/TM-291, Laboratory for Computer Science, M.I.T., 1985."},{"key":"13_CR14","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":"13_CR15","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, \u00c9. Tardos, and R. E. Tarjan. Network Flow Algorithms. In B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, editors, Flows, Paths, and VLSI Layout, pages 101\u2013164. Springer Verlag, 1990.","DOI":"10.21236\/ADA214689"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. In Proc. 18th Annual ACM Symposium on Theory of Computing, pages 136\u2013146, 1986.","DOI":"10.1145\/12130.12144"},{"key":"13_CR17","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":"13_CR18","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02288321","volume":"13","author":"D. Goldfarb","year":"1988","unstructured":"D. Goldfarb and M. D. Grigoriadis. A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Annals of Oper. Res., 13:83\u2013123, 1988.","journal-title":"Annals of Oper. Res."},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"D. S. Johnson and C. C. McGeoch, editors. Network Flows and Matching: First DIMACS Implementation Challenge. AMS, 1993.","DOI":"10.1090\/dimacs\/012"},{"key":"13_CR20","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":"13_CR21","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":"13_CR22","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":"13_CR23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0167-6377(84)90076-2","volume":"2","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan. A Simple Version of Karzanov's Blocking Flow Algorithm. Operations Research Letters, 2:265\u2013268, 1984.","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59408-6_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:27:02Z","timestamp":1605648422000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59408-6_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540594086","9783540492450"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-59408-6_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}