{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T23:33:53Z","timestamp":1773185633188,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,6,8]],"date-time":"2009-06-08T00:00:00Z","timestamp":1244419200000},"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":[[2009,6,8]]},"DOI":"10.1145\/1542362.1542426","type":"proceedings-article","created":{"date-parts":[[2009,6,9]],"date-time":"2009-06-09T12:44:24Z","timestamp":1244551464000},"page":"377-385","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Minimum cuts and shortest homologous cycles"],"prefix":"10.1145","author":[{"given":"Erin W.","family":"Chambers","sequence":"first","affiliation":[{"name":"Saint Louis University, St. Louis, MO, USA"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL, USA"}]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL, USA"}]}],"member":"320","published-online":{"date-parts":[[2009,6,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"phNetwork Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. Orlin . phNetwork Flows: Theory, Algorithms, and Applications . Prentice Hall , 1993 . R. K. Ahuja, T. L. Magnanti, and J. Orlin. phNetwork Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993."},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., 171--182, 2009. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1835\/.","author":"Borradaile G.","unstructured":"G. Borradaile , E. D. Demaine , and S. Tazari . Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs . Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., 171--182, 2009. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1835\/. G. Borradaile, E. D. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., 171--182, 2009. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1835\/."},{"key":"e_1_3_2_1_4_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 1285--1294","author":"Borradaile G.","year":"2007","unstructured":"G. Borradaile , C. Kenyon-Mathieu , and P. N. Klein . A polynomial-time approximation scheme for Steiner tree in planar graphs . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 1285--1294 , 2007 . G. Borradaile, C. Kenyon-Mathieu, and P. N. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 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.1145\/1502793.1502798"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109691"},{"key":"e_1_3_2_1_9_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97","author":"Cabello S.","year":"2007","unstructured":"S. Cabello and E. W. Chambers . Multiple source shortest paths in a genus g graph . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97 , 2007 . S. Cabello and E. W. Chambers. Multiple source shortest paths in a genus g graph. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97, 2007."},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, 527--531","author":"Cabello S.","year":"2008","unstructured":"S. Cabello , M. DeVos , J. Erickson , and B. Mohar . Finding one tight cycle . Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, 527--531 , 2008 . S. Cabello, M. DeVos, J. Erickson, and B. Mohar. Finding one tight cycle. Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, 527--531, 2008."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137918"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536453"},{"key":"e_1_3_2_1_15_1","volume-title":"Preprint","author":"Chen C.","year":"2007","unstructured":"C. Chen and D. Freedman . Quantifying homology classes II: Localization and stability . Preprint , 2007 . http:\/\/arxiv.org\/abs\/0709.2512v2. C. Chen and D. Freedman. Quantifying homology classes II: Localization and stability. Preprint, 2007. http:\/\/arxiv.org\/abs\/0709.2512v2."},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 25th Ann. Symp. Theoretical Aspects Comp. Sci., 169--180, 2008. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1343\/.","author":"Chen C.","unstructured":"C. Chen and D. Freedman . Quantifying homology classes . Proc. 25th Ann. Symp. Theoretical Aspects Comp. Sci., 169--180, 2008. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1343\/. C. Chen and D. Freedman. Quantifying homology classes. Proc. 25th Ann. Symp. Theoretical Aspects Comp. Sci., 169--180, 2008. Dagstuhl Seminar Proceedings. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1343\/."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109580"},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. 11th Sympos. Graph Drawing, 478--490","year":"2003","unstructured":"\u00c9. Colin de Verdi\u00e8re and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface . Proc. 11th Sympos. Graph Drawing, 478--490 , 2003 . Lecture Notes Comput. Sci. 2912. \u00c9. Colin de Verdi\u00e8re and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Proc. 11th Sympos. Graph Drawing, 478--490, 2003. Lecture Notes Comput. Sci. 2912."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1150-2"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255446"},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms ACM-SIAM symposium on Discrete algorithms, 278--287","author":"Demaine E. D.","year":"2007","unstructured":"E. D. Demaine , M. Hajiaghayi , and B. Mohar . Approximation algorithms via contraction decomposition . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms ACM-SIAM symposium on Discrete algorithms, 278--287 , 2007 . E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms ACM-SIAM symposium on Discrete algorithms, 278--287, 2007."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1332475.1333307"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360644"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_3_2_1_26_1","volume-title":"Diameter and treewidth in minor-closed graph families. phAlgorithmica 27:275--291","author":"Eppstein D.","year":"2000","unstructured":"D. Eppstein . Diameter and treewidth in minor-closed graph families. phAlgorithmica 27:275--291 , 2000 . D. Eppstein. Diameter and treewidth in minor-closed graph families. phAlgorithmica 27:275--291, 2000."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey . Greedy optimal homotopy and homology generators . Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046 , 2005 . J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046, 2005."},{"key":"e_1_3_2_1_29_1","volume-title":"Preprint","author":"Erickson J.","year":"2008","unstructured":"J. Erickson and P. Worah . Computing the shortest essential cycle . Preprint , November 2008 . http:\/\/www.cs.uiuc.edu\/jeffe\/pubs\/essential.html. J. Erickson and P. Worah. Computing the shortest essential cycle. Preprint, November 2008. http:\/\/www.cs.uiuc.edu\/jeffe\/pubs\/essential.html."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44485"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_3_2_1_37_1","volume-title":"phTopological graph theory","author":"Gross J. L.","year":"2001","unstructured":"J. L. Gross and T. W. Tucker . phTopological graph theory . Dover Publications , 2001 . J. L. Gross and T. W. Tucker. phTopological graph theory. Dover Publications, 2001."},{"key":"e_1_3_2_1_38_1","volume-title":"Proc. Graphics Interface, 19--26","author":"Guskov I.","year":"2001","unstructured":"I. Guskov and Z. Wood . Topological noise removal . Proc. Graphics Interface, 19--26 , 2001 . I. Guskov and Z. Wood. Topological noise removal. Proc. Graphics Interface, 19--26, 2001."},{"key":"e_1_3_2_1_39_1","volume-title":"Fundamentals of a method for evaluating rail net capacities. Tech. rep","author":"Harris T. E.","year":"1955","unstructured":"T. E. Harris and F. S. Ross . Fundamentals of a method for evaluating rail net capacities. Tech. rep ., The RAND Corporation , Santa Monica , California, October 24 1955 . Cited in s-hco-05. T. E. Harris and F. S. Ross. Fundamentals of a method for evaluating rail net capacities. Tech. rep., The RAND Corporation, Santa Monica, California, October 24 1955. Cited in s-hco-05."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214045"},{"key":"e_1_3_2_1_41_1","volume-title":"Cambridge University Press","author":"Hatcher A.","year":"2001","unstructured":"A. Hatcher . Algebraic Topology . Cambridge University Press , 2001 . http:\/\/www.math.cornell.edu\/hatcher\/. A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http:\/\/www.math.cornell.edu\/hatcher\/."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_43_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847","author":"Hochstein J. M.","year":"2007","unstructured":"J. M. Hochstein and K. Weihe . Maximum st-flow with k crossings in O(k3n log n) time . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847 , 2007 . J. M. Hochstein and K. Weihe. Maximum st-flow with k crossings in O(k3n log n) time. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847, 2007."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/646475.693316"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247107"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"issue":"1","key":"e_1_3_2_1_48_1","first-page":"37","article-title":"Minimum cut in directed planar networks","volume":"28","author":"Janiga L.","year":"1992","unstructured":"L. Janiga and V. Koubek . Minimum cut in directed planar networks . Kybernetika 28 ( 1 ): 37 -- 49 , 1992 . L. Janiga and V. Koubek. Minimum cut in directed planar networks. Kybernetika 28(1):37--49, 1992.","journal-title":"Kybernetika"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_3_2_1_50_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155","author":"Klein P.","year":"2005","unstructured":"P. Klein . Multiple-source shortest paths in planar graphs . Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155 , 2005 . P. Klein. Multiple-source shortest paths in planar graphs. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155, 2005."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496797"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"issue":"3","key":"e_1_3_2_1_54_1","first-page":"315","article-title":"Two linear time algorithms for MST on minor closed graph classes","volume":"40","author":"Mares M.","year":"2004","unstructured":"M. Mares . Two linear time algorithms for MST on minor closed graph classes . Archivum Mathematicum 40 ( 3 ): 315 -- 320 , 2004 . M. 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_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0328-8"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen . Graphs on Surfaces . Johns Hopkins University Press , 2001 . B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222073"},{"key":"e_1_3_2_1_61_1","volume-title":"On minimum spanning trees. Master's thesis","author":"Pe\u2019er D.","year":"1998","unstructured":"D. Pe\u2019er . On minimum spanning trees. Master's thesis , Hebrew University , 1998 . http:\/\/www.math.ias.edu\/avi\/STUDENTS\/dpthesis.pdf. D. Pe\u2019er. On minimum spanning trees. Master's thesis, Hebrew University, 1998. http:\/\/www.math.ias.edu\/avi\/STUDENTS\/dpthesis.pdf."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-65759-7","volume-title":"Map Color Theorem","author":"Ringel G.","year":"1974","unstructured":"G. Ringel . Map Color Theorem . Springer-Verlag , 1974 . G. Ringel. Map Color Theorem. Springer-Verlag, 1974."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.60.2.438"},{"key":"e_1_3_2_1_65_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24 . Springer-Verlag , 2003 . A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer-Verlag, 2003."},{"key":"e_1_3_2_1_66_1","volume-title":"Handbook of Discrete Optimization, 1--68","author":"Schrijver A.","year":"2005","unstructured":"A. Schrijver . On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, 1--68 , 2005 . Elsevier . A. Schrijver. On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, 1--68, 2005. Elsevier."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical Topology and Combinatorial Group Theory","author":"Stillwell J.","year":"1993","unstructured":"J. Stillwell . Classical Topology and Combinatorial Group Theory , 2 nd edition. Graduate Texts in Mathematics 72. Springer-Verlag , 1993 . J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.","edition":"2"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.002"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1538"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546945","volume-title":"phTopology and Computing","author":"Zomorodian A.","year":"2005","unstructured":"A. Zomorodian . phTopology and Computing . Cambridge University Press , 2005 . A. Zomorodian. phTopology and Computing. Cambridge University Press, 2005."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMI.2007.25"}],"event":{"name":"SoCG '09: 25th Annual Symposium on Computational Geometry","location":"Aarhus Denmark","acronym":"SoCG '09","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the twenty-fifth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1542362.1542426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1542362.1542426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:55Z","timestamp":1750253395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1542362.1542426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,8]]},"references-count":72,"alternative-id":["10.1145\/1542362.1542426","10.1145\/1542362"],"URL":"https:\/\/doi.org\/10.1145\/1542362.1542426","relation":{},"subject":[],"published":{"date-parts":[[2009,6,8]]},"assertion":[{"value":"2009-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}