{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:21:39Z","timestamp":1740097299805,"version":"3.37.3"},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_556","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T19:36:49Z","timestamp":1553110609000},"page":"1574-1576","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar Maximum Flow \u2013 Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs"],"prefix":"10.1007","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"272_CR16320","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"23","author":"R Ahuja","year":"2002","unstructured":"Ahuja R, Ergun O, Orlin J, Punnen A (2002) A survey of very large scale neighborhood search techniques. Discret Appl Math 23:75\u2013102. doi:10.1016\/S0166-218X(01)00338-9","journal-title":"Discret Appl Math"},{"key":"272_CR16321","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-45278-9_7","volume-title":"Boundary-to-boundary flows in planar graphs","author":"G Borradaile","year":"2013","unstructured":"Borradaile G, Harutyunyan A (2013) Boundary-to-boundary flows in planar graphs. In: Proceedings of IWOCA, Rouen, pp\u00a067\u201380. doi:10.1007\/978-3-642-45278-9_7"},{"key":"272_CR16322","doi-asserted-by":"crossref","unstructured":"Borradaile G, Klein PN (2009) An O ( n log n ) $$O(n\\log n)$$ algorithm for maximum st-flow in a directed planar graph. J ACM 56(2):9:1\u20139:30. doi:10.1145\/1502793.1502798, http:\/\/doi.acm.org\/10.1145\/1502793.1502798","DOI":"10.1145\/1502793.1502798"},{"key":"272_CR16323","doi-asserted-by":"crossref","unstructured":"Boykov Y, Kolmogorov V (2004) An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal Mach Intell 26(9):1124\u20131137. doi: http:\/\/dx.doi.org\/10.1109\/TPAMI.2004.60","DOI":"10.1109\/TPAMI.2004.60"},{"issue":"12","key":"272_CR16324","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"20","author":"Y Boykov","year":"2001","unstructured":"Boykov Y, Veksler O, Zabih R (2001) Efficient approximate energy minimization via graph cuts. IEEE Trans Pattern Anal Mach Intell 20(12):1222\u20131239. doi:10.1109\/TPAMI.2003.1233908","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"3","key":"272_CR16325","doi-asserted-by":"publisher","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen S, Karrenbauer A (2012) Accelerated bend minimization. J Graph Algorithm Appl 16(3):635\u2013650","journal-title":"J Graph Algorithm Appl"},{"key":"272_CR16326","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Rao S (2006) Planar graphs, negative weight edges, shortest paths, and near linear time. J\u00a0Comput\u00a0Syst Sci 72(5):868\u2013889. doi: http:\/\/dx.doi.org\/10.1016\/j.jcss.2005.05.007","DOI":"10.1016\/j.jcss.2005.05.007"},{"issue":"6","key":"272_CR16327","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","volume":"6","author":"S Geman","year":"1984","unstructured":"Geman S, Geman D (1984) Stochastic relaxation, Gibbs distributions, and the Bayesian relation of images. IEEE Trans Pattern Anal Mach Intell 6(6):721\u2013742","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"5","key":"272_CR16328","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"A Goldberg","year":"1998","unstructured":"Goldberg A, Rao S (1998) Beyond the flow decomposition barrier. J ACM 45(5):783\u2013797. doi:10.1145\/290179.290181","journal-title":"J ACM"},{"issue":"4","key":"272_CR16329","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A Goldberg","year":"1988","unstructured":"Goldberg A, Tarjan R (1988) A new approach to the maximum-flow problem. J ACM 35(4):921\u2013940","journal-title":"J ACM"},{"issue":"2","key":"272_CR16330","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1111\/j.2517-6161.1989.tb01764.x","volume":"51","author":"D Greig","year":"1989","unstructured":"Greig D, Porteous B, Seheult A (1989) Exact maximum a posteriori estimation for binary images. J R Stat Soc B 51(2):271\u2013279","journal-title":"J R Stat Soc B"},{"issue":"1","key":"272_CR16331","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger MR, Klein PN, Rao S, Subramanian S (1997) Faster shortest-path algorithms for planar graphs. J Comput Syst Sci 55(1):3\u201323. doi:10.1145\/195058.195092","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"272_CR16332","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum DS (2001) An efficient algorithm for image segmentation, Markov random fields and related problems. J ACM 48(4):686\u2013701","journal-title":"J ACM"},{"issue":"4","key":"272_CR16333","doi-asserted-by":"publisher","first-page":"992","DOI":"10.1287\/opre.1080.0524","volume":"56","author":"DS Hochbaum","year":"2008","unstructured":"Hochbaum DS (2008) The pseudoflow algorithm: a new algorithm for the maximum-flow problem. Oper Res 56(4):992\u20131009","journal-title":"Oper Res"},{"key":"272_CR16334","doi-asserted-by":"crossref","unstructured":"Johnson DB, Venkatesan SM (1983) Partition of planar flow networks. In: Proceeding of 24th FOCS, Tucson, pp\u00a0259\u2013264. doi:10.1109\/SFCS.1983.44","DOI":"10.1109\/SFCS.1983.44"},{"key":"272_CR16335","doi-asserted-by":"crossref","unstructured":"Kleinberg J, Tardos E (2002) Approximation algorithms for classification problems with pairwise relationships: metric labeling and markov random fields. J ACM 49(5):616\u2013639. doi:10.1145\/585265.585268, http:\/\/doi.acm.org\/10.1145\/585265.585268","DOI":"10.1145\/585265.585268"},{"issue":"12","key":"272_CR16336","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1109\/TPAMI.2007.1128","volume":"29","author":"P Kohli","year":"2007","unstructured":"Kohli P, Torr PHS (2007) Dynamic graph cuts for efficient inference in Markov random fields. IEEE Trans Pattern Anal Mach Intell 29(12):2079\u20132088","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"3","key":"272_CR16337","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"GL Miller","year":"1986","unstructured":"Miller GL (1986) Finding small simple cycle separators for 2-connected planar graphs. J Comput Syst Sci 32(3):265\u2013279. doi:10.1016\/0022-0000(86)90030-9","journal-title":"J Comput Syst Sci"},{"issue":"5","key":"272_CR16338","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"GL Miller","year":"1995","unstructured":"Miller GL, Naor J (1995) Flow in planar graphs with multiple sources and sinks. SIAM J Comput 24(5):1002\u20131017. doi:10.1137\/S0097539789162997","journal-title":"SIAM J Comput"},{"key":"272_CR16339","doi-asserted-by":"crossref","unstructured":"Mozes S, Wulff-Nilsen C (2010) Shortest paths in planar graphs with real lengths in O ( n log 2 n \u2215 log log n ) $$O(n\\log ^{2}n\/\\log \\log n)$$ time. In: Proceedings of 18th ESA, Liverpool, pp\u00a0206\u2013217. doi:10.1007\/978-3-642-15781-3_18","DOI":"10.1007\/978-3-642-15781-3_18"},{"key":"272_CR16340","first-page":"765","volume-title":"Max flows in O(nm) time, or better","author":"J Orlin","year":"2013","unstructured":"Orlin J (2013) Max flows in O(nm) time, or better. In: Proceedings of STOC, Palo Alto, pp\u00a0765\u2013774"},{"key":"272_CR16341","first-page":"351","volume-title":"Efficient planar graph cuts with applications in computer vision","author":"FR Schmidt","year":"2009","unstructured":"Schmidt FR, Toeppe E, Cremers D (2009) Efficient planar graph cuts with applications in computer vision. In: Proceedings of CVPR, Miami, pp\u00a0351\u2013356"},{"issue":"12","key":"272_CR16342","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1016\/j.cad.2012.06.005","volume":"44","author":"X Wei","year":"2012","unstructured":"Wei X, Joneja A, Mount DM (2012) Optimal uniformly monotone partitioning of polygons with holes. Comput Aided Des 44(12):1235\u20131252","journal-title":"Comput Aided Des"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_556","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T23:33:26Z","timestamp":1721086406000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_556"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_556","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}