{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:48:37Z","timestamp":1725853717121},"publisher-location":"New York, NY","reference-count":15,"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_683","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:15:58Z","timestamp":1553112958000},"page":"852-856","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Global Minimum Cuts in Surface-Embedded Graphs"],"prefix":"10.1007","author":[{"given":"Erin W.","family":"Chambers","sequence":"first","affiliation":[]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"159_CR7161","unstructured":"Borradaile G, Klein P (2009) An O(nlogn) algorithm for maximum st-flow in a directed planar graph. J ACM 56(2):9:1\u201330"},{"key":"159_CR7162","doi-asserted-by":"crossref","unstructured":"Cabello S (2010) Finding shortest contractible and shortest separating cycles in embedded graphs. ACM Trans Algorithms 6(2):24:1\u201324:18","DOI":"10.1145\/1721837.1721840"},{"issue":"4","key":"159_CR7163","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello S, Chambers EW, Erickson J (2013) Multiple-source shortest paths in embedded graphs. SIAM J Comput 42(4):1542\u20131571","journal-title":"SIAM J Comput"},{"issue":"3","key":"159_CR7164","doi-asserted-by":"publisher","first-page":"201","DOI":"10.7155\/jgaa.00291","volume":"17","author":"E Chambers","year":"2013","unstructured":"Chambers E, Eppstein D (2013) Flows in one-crossing-minor-free graphs. J Graph Algorithms Appl 17(3):201\u2013220. doi:10.7155\/jgaa.00291","journal-title":"J Graph Algorithms Appl"},{"issue":"1\u20132","key":"159_CR7165","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.comgeo.2007.10.010","volume":"41","author":"EW Chambers","year":"2008","unstructured":"Chambers EW, Colin de Verdi\u00e8re \u00c9, Erickson J, Lazarus F, Whittlesey K (2008) Splitting (complicated) surfaces is hard. Comput Geom Theory Appl 41(1\u20132):94\u2013110","journal-title":"Comput Geom Theory Appl"},{"key":"159_CR7166","doi-asserted-by":"crossref","unstructured":"Chambers EW, Erickson J, Nayyeri A (2009) Minimum cuts and shortest homologous cycles. In: Proceedings of the 25th annual symposium computational geometry, Aarhus, pp\u00a0377\u2013385","DOI":"10.1145\/1542362.1542426"},{"issue":"6","key":"159_CR7167","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1137\/090766863","volume":"41","author":"EW Chambers","year":"2012","unstructured":"Chambers EW, Erickson J, Nayyeri A (2012) Homology flows, cohomology cuts. SIAM J Comput 41(6):1605\u20131634","journal-title":"SIAM J Comput"},{"key":"159_CR7168","doi-asserted-by":"crossref","unstructured":"Erickson J (2012) Combinatorial optimization of cycles and bases. In: Zomorodian A (ed) Advances in applied and computational topology. Invited survey for an AMS short course on computational topology at the 2011 joint mathematics meetings, New Orleans. Proceedings of symposia in applied mathematics, vol\u00a070. American Mathematical Society, pp\u00a0195\u2013228","DOI":"10.1090\/psapm\/070\/591"},{"key":"159_CR7169","doi-asserted-by":"crossref","unstructured":"Erickson J, Nayyeri A (2011) Minimum cuts and shortest non-separating cycles via homology covers. In: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, San Francisco, pp\u00a01166\u20131176","DOI":"10.1137\/1.9781611973082.88"},{"issue":"3","key":"159_CR7170","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/jcss.1998.1592","volume":"57","author":"T Hagerup","year":"1998","unstructured":"Hagerup T, Katajainen J, Nishimura N, Ragde P (1998) Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J Comput Syst Sci 57(3):366\u2013375","journal-title":"J Comput Syst Sci"},{"key":"159_CR7171","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 Comput 8:135\u2013150","journal-title":"SIAM J Comput"},{"key":"159_CR7172","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: Proceedings of the 43rd annual ACM symposium theory of computing, San Jose, pp\u00a0313\u2013322","DOI":"10.1145\/1993636.1993679"},{"key":"159_CR7173","doi-asserted-by":"crossref","unstructured":"Kutz M (2006) Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: Proceedings of the 22nd annual symposium on computational geometry, Sedona, pp\u00a0430\u2013438","DOI":"10.1145\/1137856.1137919"},{"key":"159_CR7174","unstructured":"\u0141a\u0327cki J, Sankowski P (2011) Min-cuts and shortest cycles in planar graphs in O(nloglogn) time. In: Proceedings of the 19th annual European symposium on algorithms, Saarbr\u00fccken. Lecture notes in computer science, vol\u00a06942. Springer, pp\u00a0155\u2013166"},{"key":"159_CR7175","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1137\/0212005","volume":"12","author":"J Reif","year":"1983","unstructured":"Reif J (1983) Minimum s-t cut of a planar undirected network in O(nlog2n) time. SIAM J Comput 12:71\u201381","journal-title":"SIAM J Comput"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T21:35:45Z","timestamp":1553117745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_683","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"}}]}}