{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T14:48:20Z","timestamp":1747234100575},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_52","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"619-630","source":"Crossref","is-referenced-by-count":18,"title":["Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search"],"prefix":"10.1007","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagi","family":"Hed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pushmeet","family":"Kohli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"issue":"10","key":"52_CR1","doi-asserted-by":"publisher","first-page":"1846","DOI":"10.1109\/TPAMI.2009.194","volume":"32","author":"K. Alahari","year":"2010","unstructured":"Alahari, K., Kohli, P., Torr, P.H.S.: Dynamic hybrid algorithms for MAP inference in discrete mrfs. IEEE PAMI\u00a032(10), 1846\u20131857 (2010)","journal-title":"IEEE PAMI"},{"issue":"9","key":"52_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 PAMI\u00a026(9), 1124\u20131137 (2004)","journal-title":"IEEE PAMI"},{"key":"52_CR3","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":"52_CR4","unstructured":"Cherkassky, B.V.: A Fast Algorithm for Computing Maximum Flow in a Network. In: Karzanov, A.V. (ed.) Collected Papers, Vol. 3: Combinatorial Methods for Flow Problems, pp. 90\u201396. The Institute for Systems Studies, Moscow (1979) (in Russian) English translation appears in AMS Trans., 158, 23\u201330 (1994)"},{"key":"52_CR5","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":"52_CR6","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: 25th IEEE IPDPS, pp. 1135\u20131146 (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Exact combinatorial branch-and-bound for graph bisection. In: ALENEX, pp. 30\u201344 (2012)","DOI":"10.1137\/1.9781611972924.3"},{"key":"52_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-33090-2_36","volume-title":"Algorithms \u2013 ESA 2012","author":"D. Delling","year":"2012","unstructured":"Delling, D., Werneck, R.F.: Better bounds for graph bisection. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 407\u2013418. Springer, Heidelberg (2012)"},{"key":"52_CR9","unstructured":"Fishbain, B., Hochbaum, D.S., Mueller, S.: Competitive analysis of minimum-cut maximum flow algorithms in vision problems. CoRR, abs\/1007.4531 (2010)"},{"key":"52_CR10","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":"52_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A Fast Parametric Maximum Flow Algorithm and Applications. SIAM J. Comput.\u00a018, 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, A.: Two Level Push-Relabel Algorithm for the Maximum Flow Problem. In: Proc. 5th Alg. Aspects in Info. Management. Springer, New York (2009)","DOI":"10.1007\/978-3-642-02158-9_19"},{"key":"52_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-540-87744-8_39","volume-title":"Algorithms - ESA 2008","author":"A.V. Goldberg","year":"2008","unstructured":"Goldberg, A.V.: The partial augment\u2013relabel algorithm for the maximum flow problem. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 466\u2013477. Springer, Heidelberg (2008)"},{"key":"52_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/978-3-642-23719-5_39","volume-title":"Algorithms \u2013 ESA 2011","author":"A.V. Goldberg","year":"2011","unstructured":"Goldberg, A.V., Hed, S., Kaplan, H., Tarjan, R.E., Werneck, R.F.: Maximum flows by incremental breadth-first search. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 457\u2013468. Springer, Heidelberg (2011)"},{"key":"52_CR15","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":"52_CR16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02288321","volume":"13","author":"D. Goldfarb","year":"1988","unstructured":"Goldfarb, D., Grigoriadis, M.: A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Ann. Op. Res.\u00a013, 83\u2013123 (1988)","journal-title":"Ann. Op. Res."},{"key":"52_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J. Hao","year":"1994","unstructured":"Hao, J., Orlin, J.B.: A Faster Algorithm for Finding the Minimum Cut in a Directed Graph. J. Algorithms\u00a017, 424\u2013446 (1994)","journal-title":"J. Algorithms"},{"issue":"4","key":"52_CR18","doi-asserted-by":"publisher","first-page":"992","DOI":"10.1287\/opre.1080.0524","volume":"56","author":"D.S. Hochbaum","year":"2008","unstructured":"Hochbaum, D.S.: The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations Research\u00a056(4), 992\u20131009 (2008)","journal-title":"Operations Research"},{"issue":"12","key":"52_CR19","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1109\/TPAMI.2007.1128","volume":"29","author":"P. Kohli","year":"2007","unstructured":"Kohli, P., Torr, P.H.S.: Dynamic graph cuts for efficient inference in markov random fields. IEEE Trans. Pattern Anal. Mach. Intell.\u00a029(12), 2079\u20132088 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"52_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.cviu.2008.07.002","volume":"112","author":"P. Kohli","year":"2008","unstructured":"Kohli, P., Torr, P.H.S.: Measuring uncertainty in graph cut solutions. Computer Vision and Image Understanding\u00a0112(1), 30\u201338 (2008)","journal-title":"Computer Vision and Image Understanding"},{"issue":"2","key":"52_CR21","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1111\/j.1467-8659.2009.01400.x","volume":"28","author":"D. S\u00fdkora","year":"2009","unstructured":"S\u00fdkora, D., Dingliana, J., Collins, S.: Lazybrush: Flexible painting tool for hand-drawn cartoons. Comput. Graph. Forum\u00a028(2), 599\u2013608 (2009)","journal-title":"Comput. Graph. Forum"},{"key":"52_CR22","doi-asserted-by":"crossref","unstructured":"Verma, T., Batra, D.: Maxflow revisited: An empirical comparison of maxflow algorithms for dense vision problems. In: BMVC, pp. 1\u201312 (2012)","DOI":"10.5244\/C.26.61"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:23:27Z","timestamp":1559247807000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}