{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:21:19Z","timestamp":1740097279209,"version":"3.37.3"},"publisher-location":"New York, NY","reference-count":21,"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_626","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T19:36:49Z","timestamp":1553110609000},"page":"1576-1579","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar Maximum s- t Flow"],"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_CR16343","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0020-0190(97)00153-1","volume":"64","author":"L Coupry","year":"1997","unstructured":"Coupry L (1997) A simple linear algorithm for the edge-disjoint (s,t)-paths problem in undirected planar graphs. Inf Process Lett 64:83\u201386","journal-title":"Inf Process Lett"},{"key":"272_CR16344","unstructured":"Eisenstat D (2013) Trickle: linear-time maximum flow in planar graphs with unit capacities (java). http:\/\/www.davideisenstat.com\/trickle\/"},{"key":"272_CR16345","doi-asserted-by":"crossref","unstructured":"Erickson J (2010) Maximum flows and parametric shortest paths in planar graphs. In: 21st SODA, Austin, pp\u00a0794\u2013804","DOI":"10.1137\/1.9781611973075.65"},{"key":"272_CR16346","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"},{"key":"272_CR16347","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"C Ford","year":"1956","unstructured":"Ford C, Fulkerson D (1956) Maximal flow through a network. Can J Math 8:399\u2013404","journal-title":"Can J Math"},{"issue":"2","key":"272_CR16348","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":"3","key":"272_CR16349","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R Hassin","year":"1981","unstructured":"Hassin R (1981) Maximum flow in (s, t) planar networks. Inf Process Lett 13(3):107","journal-title":"Inf Process Lett"},{"key":"272_CR16350","doi-asserted-by":"crossref","unstructured":"Hassin R, Johnson DB (1985) An O ( n log 2 n ) $$O(n\\log ^{2}n)$$ algorithm for maximum flow in undirected planar networks. SIAM J\u00a0Comput 14:612\u2013624. doi: http:\/\/locus.siam.org\/SICOMP\/volume-14\/art_0214045.html","DOI":"10.1137\/0214045"},{"issue":"1","key":"272_CR16351","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/195058.195092","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\u00a0Comput\u00a0Syst Sci 55(1):3\u201323. doi:10.1145\/195058.195092","journal-title":"J\u00a0Comput\u00a0Syst Sci"},{"key":"272_CR16352","unstructured":"Hoch J, Wang J (2012) Max flow in a directed planar graph. https:\/\/github.com\/jrshoch\/msmsmaxflow"},{"key":"272_CR16353","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0208012","volume":"8","author":"A Itai","year":"1979","unstructured":"Itai A, Shiloach Y (1979) Maximum flow in planar networks. SIAM J\u00a0Comput 8:135\u2013150","journal-title":"SIAM J\u00a0Comput"},{"key":"272_CR16354","doi-asserted-by":"crossref","unstructured":"Italiano GF, Nussbaum Y, Sankowski P, Wulff-Nilsen C (2011) Improved algorithms for min cut and max flow in undirected planar graphs. In: 43rd STOC, San Jose, pp\u00a0313\u2013322","DOI":"10.1145\/1993636.1993679"},{"key":"272_CR16355","doi-asserted-by":"crossref","unstructured":"Johnson DB, Venkatesan SM (1983) Partition of planar flow networks. In: 24th FOCS, Tucson, pp\u00a0259\u2013264. doi:10.1109\/SFCS.1983.44","DOI":"10.1109\/SFCS.1983.44"},{"issue":"3","key":"272_CR16356","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0406038","volume":"6","author":"S Khuller","year":"1993","unstructured":"Khuller S, Naor J, Klein P (1993) The lattice structure of flow in planar graphs. SIAM J\u00a0Discret\u00a0Math 6(3):477\u2013490. doi:10.1137\/0406038","journal-title":"SIAM J\u00a0Discret\u00a0Math"},{"key":"272_CR16357","unstructured":"Klein PN (2005) Multiple-source shortest paths in planar graphs. In: 16th SODA, Vancouver, pp\u00a0146\u2013155. doi:10.1145\/1070454"},{"key":"272_CR16358","doi-asserted-by":"crossref","unstructured":"Klein PN, Mozes S, Weimann O (2010) Shortest paths in directed planar graphs with negative lengths: a linear-space O ( n log 2 n ) $$O(n\\log ^{2}n)$$ -time algorithm. TALG 6(2):1\u201318. doi: http:\/\/doi.acm.org\/10.1145\/1721837.1721846","DOI":"10.1145\/1721837.1721846"},{"issue":"5","key":"272_CR16359","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\u00a0Comput 24(5):1002\u20131017. doi:10.1137\/S0097539789162997","journal-title":"SIAM J\u00a0Comput"},{"key":"272_CR16360","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: 18th ESA, Liverpool, pp\u00a0206\u2013217"},{"key":"272_CR16361","doi-asserted-by":"crossref","unstructured":"Reif J (1983) Minimum s-t cut of a planar undirected network in O ( n log 2 n ) $$O(n\\log ^{2}n)$$ time. SIAM J\u00a0Comput 12:71\u201381. doi: http:\/\/locus.siam.org\/SICOMP\/volume-12\/art_0212005.html","DOI":"10.1137\/0212005"},{"key":"272_CR16362","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: CVPR, Miami, pp\u00a0351\u2013356"},{"key":"272_CR16363","doi-asserted-by":"crossref","unstructured":"Weihe K (1994) Edge-disjoint (s,t)-paths in undirected planar graphs in linear time. In: Proceedings of the European symposium on algorithms, Edinburgh. LNCS, vol\u00a0855, pp\u00a0130\u2013137","DOI":"10.1007\/BFb0049403"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T23:33:27Z","timestamp":1721086407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_626","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"}}]}}