{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:18Z","timestamp":1750306878200,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,17]],"date-time":"2013-06-17T00:00:00Z","timestamp":1371427200000},"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":[[2013,6,17]]},"DOI":"10.1145\/2462356.2462366","type":"proceedings-article","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T17:18:46Z","timestamp":1389115126000},"page":"249-258","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Counting and sampling minimum cuts in genus g graphs"],"prefix":"10.1145","author":[{"given":"Erin W.","family":"Chambers","sequence":"first","affiliation":[{"name":"Saint Louis University, St. Louis, MO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130210"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.017"},{"key":"e_1_3_2_1_3_1","first-page":"171","volume-title":"Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., volume 3 of Leibniz Int. Proc. Informatics","author":"Borradaile Glencora","year":"2009","unstructured":"Glencora Borradaile , Erik D. Demaine , and Siamak Tazari . Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs . In Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., volume 3 of Leibniz Int. Proc. Informatics , pages 171 -- 182 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik , 2009 . Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. In Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., volume 3 of Leibniz Int. Proc. Informatics, pages 171--182. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 2009."},{"key":"e_1_3_2_1_4_1","first-page":"1285","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms","author":"Borradaile Glencora","year":"2007","unstructured":"Glencora Borradaile , Claire Kenyon-Mathieu , and Philip N. Klein . A polynomial-time approximation scheme for Steiner tree in planar graphs . In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms , pages 1285 -- 1294 , 2007 . Glencora Borradaile, Claire Kenyon-Mathieu, and Philip N. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1285--1294, 2007."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394928"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109615"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-28831-7_5"},{"key":"e_1_3_2_1_8_1","first-page":"89","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms","author":"Cabello Sergio","year":"2007","unstructured":"Sergio Cabello and Erin W. Chambers . Multiple source shortest paths in a genus g graph . In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms , pages 89 -- 97 , 2007 . Sergio Cabello and Erin W. Chambers. Multiple source shortest paths in a genus g graph. In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 89--97, 2007."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_3_2_1_10_1","first-page":"828","volume-title":"Proc. 15th Ann. ACM-SIAM Symp. Discrete Algorithms","author":"Chalermsook Parinya","year":"2004","unstructured":"Parinya Chalermsook , Jittat Fakcharoenphol , and Danupon Nanongkai . A deterministic near-linear time algorithm for finding minimum cuts in planar graphs . In Proc. 15th Ann. ACM-SIAM Symp. Discrete Algorithms , pages 828 -- 829 , 2004 . Parinya Chalermsook, Jittat Fakcharoenphol, and Danupon Nanongkai. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In Proc. 15th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 828--829, 2004."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010","author":"Erin","year":"2010","unstructured":"Erin W. Chambers and David Eppstein. Flows in one-crossing-minor-free graphs . In Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010 ), Lecture Notes in Computer Science, pages 241--252. Springer-Verlag , 2010 . Erin W. Chambers and David Eppstein. Flows in one-crossing-minor-free graphs. In Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, pages 241--252. Springer-Verlag, 2010."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766863"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02061656"},{"key":"e_1_3_2_1_16_1","volume-title":"May","author":"de Verdi\u00e8re \u00c9ric Colin","year":"2012","unstructured":"\u00c9ric Colin de Verdi\u00e8re . Topological algorithms for graphs on surfaces. Habilitation thesis , May 2012 . \u00c9ric Colin de Verdi\u00e8re. Topological algorithms for graphs on surfaces. Habilitation thesis, May 2012."},{"key":"e_1_3_2_1_17_1","first-page":"278","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms","author":"Demaine Erik D.","year":"2007","unstructured":"Erik D. Demaine , MohammadTaghi Hajiaghayi , and Bojan Mohar . Approximation algorithms via contraction decomposition . In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms , pages 278 -- 287 , 2007 . Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. Approximation algorithms via contraction decomposition. In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 278--287, 2007."},{"key":"e_1_3_2_1_18_1","volume-title":"An Introduction","author":"Edelsbrunner Herbert","year":"2010","unstructured":"Herbert Edelsbrunner and John Harer . Computational Topology , An Introduction . American Mathematical Society , 2010 . Herbert Edelsbrunner and John Harer. Computational Topology, An Introduction. American Mathematical Society, 2010."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095219"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133139"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133124"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.26"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1592"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214045"},{"key":"e_1_3_2_1_30_1","unstructured":"Allen Hatcher. Algebraic Topology. Cambridge Univ. Press 2002. Allen Hatcher. Algebraic Topology. Cambridge Univ. Press 2002."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Mark Jerrum . Random generation of combinatiorial structures from a uniform distribution . In Wilfried Brauer editor Automata Languages and Programming volume 194 of Lecture Notes in Computer Science pages 290 -- 299 . Springer Berlin \/ Heidelberg 1985 . 10.1007\/BFb0015754. Mark Jerrum. Random generation of combinatiorial structures from a uniform distribution. In Wilfried Brauer editor Automata Languages and Programming volume 194 of Lecture Notes in Computer Science pages 290--299. Springer Berlin \/ Heidelberg 1985. 10.1007\/BFb0015754.","DOI":"10.1007\/BFb0015754"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225069"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_3_2_1_38_1","first-page":"146","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms","author":"Klein Philip","year":"2005","unstructured":"Philip Klein . Multiple-source shortest paths in planar graphs . In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms , pages 146 -- 155 , 2005 . Philip Klein. Multiple-source shortest paths in planar graphs. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 146--155, 2005."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721846"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_1_41_1","first-page":"155","volume-title":"Proc. 19th Ann. Europ. Symp. Algorithms, number 6942 in Lecture Notes Comput. Sci.","author":"\u0141cacki Jakub","year":"2011","unstructured":"Jakub \u0141cacki and Piotr Sankowski . Min-cuts and shortest cycles in planar graphs in O(n log log n) time . In Proc. 19th Ann. Europ. Symp. Algorithms, number 6942 in Lecture Notes Comput. Sci. , pages 155 -- 166 . Springer , 2011 . Jakub \u0141cacki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n) time. In Proc. 19th Ann. Europ. Symp. Algorithms, number 6942 in Lecture Notes Comput. Sci., pages 155--166. Springer, 2011."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"issue":"3","key":"e_1_3_2_1_43_1","first-page":"315","article-title":"Two linear time algorithms for MST on minor closed graph classes","volume":"40","author":"Mares Martin","year":"2004","unstructured":"Martin Mares . Two linear time algorithms for MST on minor closed graph classes . Archivum Mathematicum , 40 ( 3 ): 315 -- 320 , 2004 . Martin Mares. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum, 40(3):315--320, 2004.","journal-title":"Archivum Mathematicum"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","year":"2001","unstructured":"Bojan Mohar and Carsten Thomassen . Graphs on Surfaces . Johns Hopkins Univ. Press , 2001 . Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins Univ. Press, 2001."},{"key":"e_1_3_2_1_46_1","first-page":"206","volume-title":"Proc. 18th Ann. Europ. Symp. Algorithms, number 6347 in Lecture Notes Comput. Sci.","author":"Mozes Shay","year":"2010","unstructured":"Shay Mozes and Christian Wulff-Nilsen . Shortest paths in planar graphs with real lengths in O(n log^2n\/log log n) time . In Proc. 18th Ann. Europ. Symp. Algorithms, number 6347 in Lecture Notes Comput. Sci. , pages 206 -- 217 . Springer-Verlag , 2010 . Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in O(n log^2n\/log log n) time. In Proc. 18th Ann. Europ. Symp. Algorithms, number 6347 in Lecture Notes Comput. Sci., pages 206--217. Springer-Verlag, 2010."},{"key":"e_1_3_2_1_47_1","volume-title":"Prentice-Hall","author":"Munkres James R.","year":"2000","unstructured":"James R. Munkres . Topology. Prentice-Hall , 2 nd edition, 2000 . James R. Munkres. Topology. Prentice-Hall, 2nd edition, 2000.","edition":"2"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/24.106785"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888999"},{"key":"e_1_3_2_1_50_1","volume-title":"On minimum spanning trees. Master's thesis","author":"Pe'er Dana","year":"1998","unstructured":"Dana Pe'er . On minimum spanning trees. Master's thesis , Hebrew University , 1998 . Dana Pe'er. On minimum spanning trees. Master's thesis, Hebrew University, 1998."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01103.x"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.002"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1538"},{"key":"e_1_3_2_1_56_1","first-page":"353","volume-title":"Orientable embeddings of cayley graphs. Duke math J","author":"White A.","year":"1974","unstructured":"A. White . Orientable embeddings of cayley graphs. Duke math J ., pages 353 -- 371 , 1974 . A. White. Orientable embeddings of cayley graphs. Duke math J., pages 353--371, 1974."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873663"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1050943"}],"event":{"name":"SoCG '13: Symposium on Computational Geometry 2013","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rio de Janeiro Brazil","acronym":"SoCG '13"},"container-title":["Proceedings of the twenty-ninth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462366","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2462356.2462366","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:29Z","timestamp":1750234709000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,17]]},"references-count":58,"alternative-id":["10.1145\/2462356.2462366","10.1145\/2462356"],"URL":"https:\/\/doi.org\/10.1145\/2462356.2462366","relation":{},"subject":[],"published":{"date-parts":[[2013,6,17]]},"assertion":[{"value":"2013-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}