{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T18:55:31Z","timestamp":1766516131155,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,5,31]],"date-time":"2009-05-31T00:00:00Z","timestamp":1243728000000},"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,5,31]]},"DOI":"10.1145\/1536414.1536453","type":"proceedings-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T14:51:13Z","timestamp":1243954273000},"page":"273-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Homology flows, cohomology cuts"],"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":"Jeff","family":"Erickson","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,5,31]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241928"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"e_1_3_2_1_4_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , 1993 . R. K. Ahuja, T. L. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194272183"},{"key":"e_1_3_2_1_6_1","volume-title":"Polynomial algorithms for Lagrangean relaxations in combinatorial problems","author":"Aneja Y. P.","year":"1991","unstructured":"Y. P. Aneja and S. N. Kabadi . Polynomial algorithms for Lagrangean relaxations in combinatorial problems . Faculty of Business Working Paper Series W91-03, University of Windsor , 1991 . Cited in ka-eapof-01. Y. P. Aneja and S. N. Kabadi. Polynomial algorithms for Lagrangean relaxations in combinatorial problems. Faculty of Business Working Paper Series W91-03, University of Windsor, 1991. Cited in ka-eapof-01."},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. 25th Symp. Math. Found. Comput. Sci., 192--201, 2000","author":"Biedl T. C.","year":"1893","unstructured":"T. C. Biedl , B. Brejov\u00e1 , and T. Vinar . Simplifying flow networks . Proc. 25th Symp. Math. Found. Comput. Sci., 192--201, 2000 . Lecture Notes Comput. Sci. 1893 , Springer-Verlag. T. C. Biedl, B. Brejov\u00e1, and T. Vinar. Simplifying flow networks. Proc. 25th Symp. Math. Found. Comput. Sci., 192--201, 2000. Lecture Notes Comput. Sci. 1893, Springer-Verlag."},{"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.","key":"e_1_3_2_1_9_1","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_10_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_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394928"},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, 524--533","author":"Borradaile G.","year":"2006","unstructured":"G. Borradaile and P. Klein . An O(n log n)-time algorithm for maximum st-flow in a directed planar graph . Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, 524--533 , 2006 . G. Borradaile and P. Klein. An O(n log n)-time algorithm for maximum st-flow in a directed planar graph. Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, 524--533, 2006."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502798"},{"key":"e_1_3_2_1_14_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_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426"},{"key":"e_1_3_2_1_18_1","volume-title":"Maximizing concave functions in fixed dimension. Complexity in Numerical Optimization, 74--87","author":"Cohen E.","year":"1993","unstructured":"E. Cohen and N. Megiddo . Maximizing concave functions in fixed dimension. Complexity in Numerical Optimization, 74--87 , 1993 . World Scientific . E. Cohen and N. Megiddo. Maximizing concave functions in fixed dimension. Complexity in Numerical Optimization, 74--87, 1993. World Scientific."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153727"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01240739"},{"key":"e_1_3_2_1_21_1","volume-title":"18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287","author":"Demaine E. D.","year":"2007","unstructured":"E. D. Demaine , M. Hajiaghayi , and B. Mohar . Approximation algorithms via contraction decomposition. phProc . 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287 , 2007 . E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. phProc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287, 2007."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647676.731827"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608","author":"Eppstein D.","year":"2003","unstructured":"D. Eppstein . Dynamic generators of topologically embedded graphs . Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608 , 2003 . D. Eppstein. Dynamic generators of topologically embedded graphs. Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608, 2003."},{"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","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_3_2_1_36_1","volume-title":"Topological graph theory","author":"Gross J. L.","year":"2001","unstructured":"J. L. Gross and T. W. Tucker . Topological graph theory . Dover Publications , 2001 . J. L. Gross and T. W. Tucker. Topological graph theory. Dover Publications, 2001."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"phGeometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel M.","year":"1993","unstructured":"M. Gr\u00f6tschel , L. Lov\u00e1sz , and A. Schrijver . phGeometric Algorithms and Combinatorial Optimization , 2 nd edition. Algorithms and Combinatorics 2. Springer-Verlag , 1993 . M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. phGeometric Algorithms and Combinatorial Optimization, 2nd edition. Algorithms and Combinatorics 2. Springer-Verlag, 1993.","edition":"2"},{"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.1016\/0020-0190(81)90120-4"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214045"},{"key":"e_1_3_2_1_42_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_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_44_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 s-t-flow with k crossings in O(k<sup>3<\/sup>n log n) time . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847 , 2007 . J. M. Hochstein and K. Weihe. Maximum s-t-flow with k crossings in O(k<sup>3<\/sup>n log n) time. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 843--847, 2007."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_3_2_1_46_1","volume-title":"Proc. AMS-IMS-SIAM Joint Summer Res. Conf., 19--26","author":"Hutchinson J. P.","year":"1989","unstructured":"J. P. Hutchinson . On genus-reducing and planarizing algorithms for embedded graphs. Graphs and Algorithms , Proc. AMS-IMS-SIAM Joint Summer Res. Conf., 19--26 , 1989 . Contemporary Mathematics 89, American Mathematical Society. J. P. Hutchinson. On genus-reducing and planarizing algorithms for embedded graphs. Graphs and Algorithms, Proc. AMS-IMS-SIAM Joint Summer Res. Conf., 19--26, 1989. Contemporary Mathematics 89, American Mathematical Society."},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the Japan-US Joint Seminar","author":"Hutchinson J. P.","year":"1987","unstructured":"J. P. Hutchinson and G. L. Miller . Deleting vertices to make graphs of positive genus planar. Discrete Algorithms and Complexity Theory , Proceedings of the Japan-US Joint Seminar , Kyoto, Japan, 81--98 , 1987 . Academic Press. J. P. Hutchinson and G. L. Miller. Deleting vertices to make graphs of positive genus planar. Discrete Algorithms and Complexity Theory, Proceedings of the Japan-US Joint Seminar, Kyoto, Japan, 81--98, 1987. Academic Press."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/646475.693316"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.44"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00028-3"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010073"},{"key":"e_1_3_2_1_53_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_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496797"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"issue":"3","key":"e_1_3_2_1_57_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_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-9063-4"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_3_2_1_62_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_63_1","volume-title":"J. R. Munkres. Topology","year":"2000","unstructured":"J. R. Munkres. Topology , 2 nd edition. Prentice-Hall , 2000 . J. R. Munkres. Topology, 2nd edition. Prentice-Hall, 2000.","edition":"2"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90006-X"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222073"},{"key":"e_1_3_2_1_67_1","volume-title":"On minimum spanning trees. Master's thesis","author":"Pe'er D.","year":"1998","unstructured":"D. Pe'er . On minimum spanning trees. Master's thesis , Hebrew University , 1998 . http:\/\/www.math.ias.edu\/ avi\/STUDENTS\/dpthesis.pdf. D. Pe'er. 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_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_1_69_1","volume-title":"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_70_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_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.002"},{"key":"e_1_3_2_1_73_1","volume-title":"Complexity in Numerical Optimization, 429--447","author":"Toledo S.","year":"1993","unstructured":"S. Toledo . Maximizing non-linear concave functions in fixed dimension. Complexity in Numerical Optimization, 429--447 , 1993 . World Scientific . S. Toledo. Maximizing non-linear concave functions in fixed dimension. Complexity in Numerical Optimization, 429--447, 1993. World Scientific."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_75_1","volume-title":"thesis","author":"Venkatesan S. M.","year":"1983","unstructured":"S. M. Venkatesan . Algorithms for network flows. Ph . D. thesis , The Pennsylvania State University , 1983 . Cited in jv-ppfn-83. S. M. Venkatesan. Algorithms for network flows. Ph.D. thesis, The Pennsylvania State University, 1983. Cited in jv-ppfn-83."},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0831"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1538"}],"event":{"name":"STOC '09: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Bethesda MD USA","acronym":"STOC '09"},"container-title":["Proceedings of the forty-first annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1536414.1536453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1536414.1536453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:51Z","timestamp":1750253931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1536414.1536453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,31]]},"references-count":74,"alternative-id":["10.1145\/1536414.1536453","10.1145\/1536414"],"URL":"https:\/\/doi.org\/10.1145\/1536414.1536453","relation":{},"subject":[],"published":{"date-parts":[[2009,5,31]]},"assertion":[{"value":"2009-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}