{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:09:24Z","timestamp":1742940564539,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_39","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"457-468","source":"Crossref","is-referenced-by-count":31,"title":["Maximum Flows by Incremental Breadth-First Search"],"prefix":"10.1007","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[]},{"given":"Sagi","family":"Hed","sequence":"additional","affiliation":[]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1007\/978-3-642-15558-1_40","volume-title":"ECCV 2010, Part III","author":"C. Arora","year":"2010","unstructured":"Arora, C., Banerjee, S., Kalra, P., Maheshwari, S.: An Efficient Graph Cut Algorithm for Computer Vision Problems. In: Daniilidis, K. (ed.) ECCV 2010, Part III. LNCS, vol.\u00a06313, pp. 552\u2013565. Springer, Heidelberg (2010)"},{"issue":"9","key":"39_CR2","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","volume":"26","author":"Y. Boykov","year":"2004","unstructured":"Boykov, Y., Kolmogorov, V.: An Experimental Comparison of Min-Cut\/Max-Flow Algorithms for Energy Minimization in Vision. IEEE transactions on Pattern Analysis and Machine Intelligence\u00a026(9), 1124\u20131137 (2004)","journal-title":"IEEE transactions on Pattern Analysis and Machine Intelligence"},{"key":"39_CR3","first-page":"109","volume-title":"Handbook of Mathematical Models in Computer Vision","author":"Y. Boykov","year":"2006","unstructured":"Boykov, Y., Veksler, O.: Graph Cuts in Vision and Graphics: Theories and Applications. In: Paragios, N., Chen, Y., Faugeras, O. (eds.) Handbook of Mathematical Models in Computer Vision, pp. 109\u2013131. Springer, Heidelberg (2006)"},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1287\/opre.1080.0572","volume":"57","author":"B. Chandran","year":"2009","unstructured":"Chandran, B., Hochbaum, D.: A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem. Operations Research\u00a057, 358\u2013376 (2009)","journal-title":"Operations Research"},{"key":"#cr-split#-39_CR5.1","unstructured":"Cherkassky, B.V.: A Fast Algorithm for Computing Maximum Flow in a Network. In: Karzanov, A.V. (ed.) Collected Papers. Combinatorial Methods for Flow Problems, vol.\u00a03, pp. 90-96. The Institute for Systems Studies, Moscow (1979) (in Russian)"},{"key":"#cr-split#-39_CR5.2","unstructured":"English translation appears in AMS Trans. 158, 23-30 (1994)"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"B.V. Cherkassky","year":"1997","unstructured":"Cherkassky, B.V., Goldberg, A.V.: On Implementing Push-Relabel Method for the Maximum Flow Problem. Algorithmica\u00a019, 390\u2013410 (1997)","journal-title":"Algorithmica"},{"key":"39_CR7","first-page":"359","volume-title":"Activity Analysis and Production and Allocation","author":"G.B. Dantzig","year":"1951","unstructured":"Dantzig, G.B.: Application of the Simplex Method to a Transportation Problem. In: Koopmans, T.C. (ed.) Activity Analysis and Production and Allocation, pp. 359\u2013373. Wiley, New York (1951)"},{"key":"39_CR8","first-page":"1277","volume":"11","author":"E.A. Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl.\u00a011, 1277\u20131280 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford Jr.","year":"1956","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Maximal Flow Through a Network. Canadian Journal of Math.\u00a08, 399\u2013404 (1956)","journal-title":"Canadian Journal of Math."},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-642-02158-9_19","volume-title":"Algorithmic Aspects in Information and Management","author":"A.V. Goldberg","year":"2009","unstructured":"Goldberg, A.V.: Two-Level Push-Relabel Algorithm for the Maximum Flow Problem. In: Goldberg, A.V., Zhou, Y. (eds.) AAIM 2009. LNCS, vol.\u00a05564, pp. 212\u2013225. Springer, Heidelberg (2009)"},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290181","volume":"45","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the Flow Decomposition Barrier. J. Assoc. Comput. Mach.\u00a045, 753\u2013782 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach.\u00a035, 921\u2013940 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"39_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02288321","volume":"13","author":"D. Goldfarb","year":"1988","unstructured":"Goldfarb, D., Grigoriadis, M.D.: A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Annals of Oper. Res.\u00a013, 83\u2013123 (1988)","journal-title":"Annals of Oper. Res."},{"key":"39_CR14","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/012","volume-title":"Network Flows and Matching: First DIMACS Implementation Challenge","author":"D.S. Johnson","year":"1993","unstructured":"Johnson, D.S., McGeoch, C.C.: Network Flows and Matching: First DIMACS Implementation Challenge. AMS, Providence (1993)"},{"key":"39_CR15","first-page":"434","volume":"15","author":"A.V. Karzanov","year":"1974","unstructured":"Karzanov, A.V.: Determining the Maximal Flow in a Network by the Method of Preflows. Soviet Math. Dok.\u00a015, 434\u2013437 (1974)","journal-title":"Soviet Math. Dok."},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1006\/jagm.1994.1044","volume":"17","author":"V. King","year":"1994","unstructured":"King, V., Rao, S., Tarjan, R.: A Faster Deterministic Maximum Flow Algorithm. J. Algorithms\u00a017, 447\u2013474 (1994)","journal-title":"J. Algorithms"},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A Data Structure for Dynamic Trees. J. Comput. System Sci.\u00a026, 362\u2013391 (1983)","journal-title":"J. Comput. System Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:24:26Z","timestamp":1558297466000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}