{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:53Z","timestamp":1750221233654,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":79,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-15-1-0408"],"award-info":[{"award-number":["W911NF-15-1-0408"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1408763,IIS-1408846,IIS-1447554,CCF-1513816,CCF-1546392,CCF-1527084,CCF-1535972"],"award-info":[{"award-number":["CCF-1408763,IIS-1408846,IIS-1447554,CCF-1513816,CCF-1546392,CCF-1527084,CCF-1535972"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188904","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1319-1332","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Holiest minimum-cost paths and flows in surface graphs"],"prefix":"10.1145","author":[{"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luvsandondov","family":"Lkhamsuren","sequence":"additional","affiliation":[{"name":"Airbnb, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Claude Berge and Alain Ghouilla-Houri. 1965.  Claude Berge and Alain Ghouilla-Houri. 1965."},{"key":"e_1_3_2_2_2_1","unstructured":"Programming Games and Transportation Networks. Methuen & Co.  Programming Games and Transportation Networks. Methuen & Co."},{"key":"e_1_3_2_2_3_1","volume-title":"Kyle Fox, and Amir Nayyeri.","author":"Borradaile Glencora","year":"2017","unstructured":"Glencora Borradaile , Erin Wolf Chambers , Kyle Fox, and Amir Nayyeri. 2017 . Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. 2017."},{"key":"e_1_3_2_2_4_1","volume-title":"58\u201379","author":"Comput Minimum","year":"2017","unstructured":"Minimum cycle and homology bases of surface-embedded graphs. J. Comput . Geom. 8, 2 ( 2017 ), 58\u201379 . Minimum cycle and homology bases of surface-embedded graphs. J. Comput. Geom. 8, 2 (2017), 58\u201379."},{"key":"e_1_3_2_2_5_1","volume-title":"Proc. 32nd Intern. Symp. Comput. Geom. 22:1\u201322:16","author":"Borradaile Glencora","year":"2016","unstructured":"Glencora Borradaile , David Eppstein , Amir Nayyeri , and Christian Wulff-Nilsen . 2016 . All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs . In Proc. 32nd Intern. Symp. Comput. Geom. 22:1\u201322:16 . Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. 2016. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In Proc. 32nd Intern. Symp. Comput. Geom. 22:1\u201322:16."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502798"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1042929"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684068"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490274"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010029"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_17"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"key":"e_1_3_2_2_13_1","unstructured":"Sergio Cabello Erin W. Chambers and Jeff Erickson. 2013.  Sergio Cabello Erin W. Chambers and Jeff Erickson. 2013."},{"key":"e_1_3_2_2_14_1","volume-title":"1542\u20131571","author":"Comput SIAM J.","year":"2013","unstructured":"Multiple-source shortest paths in embedded graphs. SIAM J. Comput . 42, 4 ( 2013 ), 1542\u20131571 . Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42, 4 (2013), 1542\u20131571."},{"key":"e_1_3_2_2_15_1","unstructured":"Erin W. Chambers Jeff Erickson and Amir Nayyeri. 2012.  Erin W. Chambers Jeff Erickson and Amir Nayyeri. 2012."},{"key":"e_1_3_2_2_16_1","series-title":"SIAM J. Comput. 41, 6","volume-title":"cohomology cuts","author":"Homology","year":"2012","unstructured":"Homology flows , cohomology cuts . SIAM J. Comput. 41, 6 ( 2012 ), 1605\u20131634. Homology flows, cohomology cuts. SIAM J. Comput. 41, 6 (2012), 1605\u20131634."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9623-4"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832033"},{"key":"e_1_3_2_2_19_1","unstructured":"Abraham Charnes. 1952.  Abraham Charnes. 1952."},{"key":"e_1_3_2_2_20_1","volume-title":"160\u2013170","author":"Optimality","year":"1952","unstructured":"Optimality and degeneracy in linear programming. Econometrica 20, 2 ( 1952 ), 160\u2013170 . Optimality and degeneracy in linear programming. Econometrica 20, 2 (1952), 160\u2013170."},{"key":"e_1_3_2_2_21_1","volume-title":"Topological algorithms for graphs on surfaces. (May","author":"de Verdi\u00e8re \u00c9ric Colin","year":"2012","unstructured":"\u00c9ric Colin de Verdi\u00e8re . 2012. Topological algorithms for graphs on surfaces. (May 2012 ). Habilitation thesis. \u00c9ric Colin de Verdi\u00e8re. 2012. Topological algorithms for graphs on surfaces. (May 2012). Habilitation thesis."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580379"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.183"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.11.002"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_2_26_1","volume-title":"Harer","author":"Edelsbrunner Herbert","year":"2010","unstructured":"Herbert Edelsbrunner and John L . Harer . 2010 . Herbert Edelsbrunner and John L. Harer. 2010."},{"key":"e_1_3_2_2_27_1","unstructured":"Computational Topology: An Introduction. Amer. Math. Soc.  Computational Topology: An Introduction. Amer. Math. Soc."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488702"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873666"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998231"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095219"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133124"},{"key":"e_1_3_2_2_34_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 1038\u20131046","author":"Erickson Jeff","year":"2005","unstructured":"Jeff Erickson and Kim Whittlesey . 2005 . Greedy optimal homotopy and homology generators . In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 1038\u20131046 . Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 1038\u20131046."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115964.3116089"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627843"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480190177042"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90120-4"},{"key":"e_1_3_2_2_40_1","unstructured":"Allen Hatcher. 2002.  Allen Hatcher. 2002."},{"key":"e_1_3_2_2_41_1","unstructured":"Algebraic Topology. Cambridge Univ. Press. http:\/\/www. math.cornell.edu\/~hatcher\/AT\/ATpage.html  Algebraic Topology. Cambridge Univ. Press. http:\/\/www. math.cornell.edu\/~hatcher\/AT\/ATpage.html"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_2_2_43_1","unstructured":"Monika R. Henzinger Philip Klein Satish Rao and Sairam Subramanian. 1997.  Monika R. Henzinger Philip Klein Satish Rao and Sairam Subramanian. 1997."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.44"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90026-3"},{"key":"e_1_3_2_2_49_1","volume-title":"Proc. 38th Int. Colloq. Automata Lang. Prog. (Lecture Notes Comput. Sci.)","volume":"6755","author":"Klein Philip N.","year":"2011","unstructured":"Ken-ichi Kawarabayashi, Philip N. Klein , and Christian Sommer . 2011 . Linearspace approximate distance oracles for planar, bounded-genus and minor-free graphs . In Proc. 38th Int. Colloq. Automata Lang. Prog. (Lecture Notes Comput. Sci.) , Vol. 6755 . Springer-Verlag, 135\u2013146. Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer. 2011. Linearspace approximate distance oracles for planar, bounded-genus and minor-free graphs. In Proc. 38th Int. Colloq. Automata Lang. Prog. (Lecture Notes Comput. Sci.), Vol. 6755. Springer-Verlag, 135\u2013146."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406038"},{"key":"e_1_3_2_2_51_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 146\u2013155","author":"Klein Philip","year":"2005","unstructured":"Philip Klein . 2005 . Multiple-source shortest paths in planar graphs . In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 146\u2013155 . Philip Klein. 2005. Multiple-source shortest paths in planar graphs. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 146\u2013155."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721846"},{"key":"e_1_3_2_2_53_1","unstructured":"Jakub \u0141\u0105cki Yahav Nussbaum Piotr Sankowski and Christian Wulff-Nilsen. 2012.  Jakub \u0141\u0105cki Yahav Nussbaum Piotr Sankowski and Christian Wulff-Nilsen. 2012."},{"volume-title":"Source - All Sinks Max Flows in Planar Digraphs. In Proc. 53rd IEEE Symp. Found. Comput. Sci. 599\u2013608","author":"Single","key":"e_1_3_2_2_54_1","unstructured":"Single Source - All Sinks Max Flows in Planar Digraphs. In Proc. 53rd IEEE Symp. Found. Comput. Sci. 599\u2013608 . Single Source - All Sinks Max Flows in Planar Digraphs. In Proc. 53rd IEEE Symp. Found. Comput. Sci. 599\u2013608."},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1939238.1939270"},{"key":"e_1_3_2_2_56_1","unstructured":"Bojan Mohar and Carsten Thomassen. 2001.  Bojan Mohar and Carsten Thomassen. 2001."},{"volume-title":"Johns Hopkins Univ","author":"Surfaces Graphs","key":"e_1_3_2_2_57_1","unstructured":"Graphs on Surfaces . Johns Hopkins Univ . Press . Graphs on Surfaces. Johns Hopkins Univ. Press."},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175302"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095135"},{"key":"e_1_3_2_2_60_1","volume-title":"Proc. 18th Ann. Europ. Symp. Algorithms (Lecture Notes Comput. Sci.). Springer-Verlag, 206\u2013217","author":"Mozes Shay","year":"2010","unstructured":"Shay Mozes and Christian Wulff-Nilsen . 2010 . Shortest paths in planar graphs with real lengths in O(n log 2 n\/log log n) time . In Proc. 18th Ann. Europ. Symp. Algorithms (Lecture Notes Comput. Sci.). Springer-Verlag, 206\u2013217 . Shay Mozes and Christian Wulff-Nilsen. 2010. Shortest paths in planar graphs with real lengths in O(n log 2 n\/log log n) time. In Proc. 18th Ann. Europ. Symp. Algorithms (Lecture Notes Comput. Sci.). Springer-Verlag, 206\u2013217."},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_2_62_1","unstructured":"James R. Munkres. 2000.  James R. Munkres. 2000."},{"edition":"2","volume-title":"Topology","key":"e_1_3_2_2_63_1","unstructured":"Topology ( 2 nd ed.). Prentice-Hall . Topology (2nd ed.). Prentice-Hall."},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167284"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811416"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793253565"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614369"},{"key":"e_1_3_2_2_68_1","volume-title":"Werneck","author":"Tarjan Robert E.","year":"2005","unstructured":"Robert E. Tarjan and Renato F . Werneck . 2005 . Self-adjusting top trees. In Proc. 16th Ann. ACM-SIAM Symp . Discrete Algorithms. 813\u2013822. Robert E. Tarjan and Renato F. Werneck. 2005. Self-adjusting top trees. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms. 813\u2013822."},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.03.002"},{"key":"e_1_3_2_2_70_1","unstructured":"Shankar M. Venkatesan. 1983.  Shankar M. Venkatesan. 1983."},{"volume-title":"thesis","author":"Ph Algorithms","key":"e_1_3_2_2_71_1","unstructured":"Algorithms for network flows. Ph . D. thesis . The Pennsylvania State University . Cited in { 39 }. Algorithms for network flows. Ph.D. thesis. The Pennsylvania State University. Cited in { 39 }."},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0831"},{"key":"e_1_3_2_2_73_1","unstructured":"Karsten Weihe. 1997.  Karsten Weihe. 1997."},{"key":"e_1_3_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1538"},{"key":"e_1_3_2_2_75_1","volume-title":"Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time. Preprint. (December","author":"Wulff-Nilsen Christian","year":"2009","unstructured":"Christian Wulff-Nilsen . 2009. Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time. Preprint. (December 2009 ). Christian Wulff-Nilsen. 2009. Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time. Preprint. (December 2009)."},{"key":"e_1_3_2_2_76_1","volume-title":"Orlin","author":"Young Neal E.","year":"1991","unstructured":"Neal E. Young , Robert E. Tarjan , and James B . Orlin . 1991 . Neal E. Young, Robert E. Tarjan, and James B. Orlin. 1991."},{"key":"e_1_3_2_2_77_1","volume-title":"Networks 21, 2","author":"Faster","year":"1991","unstructured":"Faster parametric shortest path and minimum balance algorithms. Networks 21, 2 ( 1991 ), 205\u2013221. Faster parametric shortest path and minimum balance algorithms. Networks 21, 2 (1991), 205\u2013221."},{"key":"e_1_3_2_2_78_1","unstructured":"Afra Zomorodian. 2005.  Afra Zomorodian. 2005."},{"key":"e_1_3_2_2_79_1","unstructured":"Topology for Computing. Cambridge Univ. Press.   Topology for Computing. Cambridge Univ. Press."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188904","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":79,"alternative-id":["10.1145\/3188745.3188904","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188904","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}