{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T22:41:19Z","timestamp":1768516879719,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993679","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"313-322","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Improved algorithms for min cut and max flow in undirected planar graphs"],"prefix":"10.1145","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[{"name":"University Rome , Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Wulff-Nilsen","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_3_2_2_2_1","first-page":"89","volume-title":"SODA: Proc. 18th Annual ACM-SIAM Symposium","author":"Cabello S.","year":"2007","unstructured":"S. Cabello and E. W. Chambers . Multiple source shortest paths in a genus g graph . In SODA: Proc. 18th Annual ACM-SIAM Symposium , pages 89 -- 97 , 2007 . S. Cabello and E. W. Chambers. Multiple source shortest paths in a genus g graph. In SODA: Proc. 18th Annual ACM-SIAM Symposium, pages 89--97, 2007."},{"key":"e_1_3_2_2_3_1","first-page":"828","volume-title":"SODA: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chalermsook P.","year":"2004","unstructured":"P. Chalermsook , J. Fakcharoenphol , and D. Nanongkai . A deterministic near-linear time algorithm for finding minimum cuts in planar graphs . In SODA: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 828 -- 829 , 2004 . P. Chalermsook, J. Fakcharoenphol, and D. Nanongkai. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In SODA: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 828--829, 2004."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133124"},{"key":"e_1_3_2_2_6_1","first-page":"1038","volume-title":"SODA: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey . Greedy optimal homotopy and homology generators . In SODA: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1038 -- 1046 , 2005 . J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. In SODA: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1038--1046, 2005."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_2_9_1","volume-title":"Flows in Network","author":"Ford L. R.","year":"1962","unstructured":"L. R. Ford and D. R. Fulkerson . Flows in Network . Princeton Univ. Press , 1962 . L. R. Ford and D. R. Fulkerson. Flows in Network. Princeton Univ. Press, 1962."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_2_2_14_1","volume-title":"Maximum flows in (s, t) planar networks. IPL, page 107","author":"Hassin R.","year":"1981","unstructured":"R. Hassin . Maximum flows in (s, t) planar networks. IPL, page 107 , 1981 . R. Hassin. Maximum flows in (s, t) planar networks. IPL, page 107, 1981."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214045"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31849"},{"key":"e_1_3_2_2_19_1","first-page":"117","volume-title":"28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011","author":"Kaplan H.","year":"2011","unstructured":"H. Kaplan and Y. Nussbaum . Minimum s-t cut in undirected planar graphs when the source and the sink are close . In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011 ), LIPIcs 9, pages 117 -- 128 , 2011 . H. Kaplan and Y. Nussbaum. Minimum s-t cut in undirected planar graphs when the source and the sink are close. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), LIPIcs 9, pages 117--128, 2011."},{"key":"e_1_3_2_2_20_1","first-page":"146","volume-title":"SODA '05: Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms","author":"Klein P. N.","year":"2005","unstructured":"P. N. Klein . Multiple-source shortest paths in planar graphs . In SODA '05: Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms , pages 146 -- 155 , 2005 . P. N. Klein. Multiple-source shortest paths in planar graphs. In SODA '05: Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms, pages 146--155, 2005."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767868"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:10Z","timestamp":1750244770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":25,"alternative-id":["10.1145\/1993636.1993679","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993679","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}