{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,12]],"date-time":"2025-04-12T10:06:51Z","timestamp":1744452411978,"version":"3.37.3"},"publisher-location":"New York, NY, USA","reference-count":89,"publisher":"ACM","funder":[{"name":"Swedish Research Council","award":["2019-05622"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585219","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1229-1242","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Algorithms via Dynamic-Oracle Matroids"],"prefix":"10.1145","author":[{"given":"Joakim","family":"Blikstad","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Sweden"}]},{"given":"Sagnik","family":"Mukhopadhyay","sequence":"additional","affiliation":[{"name":"University of Sheffield, UK"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"MPI-INF, Germany \/ KTH Royal Institute of Technology, Sweden"}]},{"given":"Ta-Wei","family":"Tu","sequence":"additional","affiliation":[{"name":"MPI-INF, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00088"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00112"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451073"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.143"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/1995784"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461797"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_33"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207169108803956"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00055"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00018"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00059"},{"volume-title":"Fast edge splitting and Edmonds","author":"Bhalgat Anand","key":"e_1_3_2_1_13_1","unstructured":"Anand Bhalgat , Ramesh Hariharan , Telikepalli Kavitha , and Debmalya Panigrahi . 2008. Fast edge splitting and Edmonds \u2019 arborescence construction for unweighted graphs. In SODA. SIAM , 455\u2013464. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347132 Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2008. Fast edge splitting and Edmonds\u2019 arborescence construction for unweighted graphs. In SODA. SIAM, 455\u2013464. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347132"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.31"},{"key":"e_1_3_2_1_15_1","volume-title":"Fast Algorithms via Dynamic-Oracle Matroids. CoRR, abs\/2302.09796","author":"Blikstad Joakim","year":"2023","unstructured":"Joakim Blikstad , Sagnik Mukhopadhyay , Danupon Nanongkai , and Ta-Wei Tu. 2023. Fast Algorithms via Dynamic-Oracle Matroids. CoRR, abs\/2302.09796 ( 2023 ), https:\/\/doi.org\/10.48550\/arXiv.2302.09796 arXiv:2302.09796. 10.48550\/arXiv.2302.09796 Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu. 2023. Fast Algorithms via Dynamic-Oracle Matroids. CoRR, abs\/2302.09796 (2023), https:\/\/doi.org\/10.48550\/arXiv.2302.09796 arXiv:2302.09796."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00113"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451092"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38919-2_5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_50"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch95"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00113"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.127"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00030"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00072"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.48"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215066"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_8"},{"key":"e_1_3_2_1_30_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic Efim A","year":"1970","unstructured":"Efim A Dinic . 1970 . Algorithm for solution of a problem of maximum flow in networks with power estimation . In Soviet Math. Doklady. 11 , 1277 \u2013 1280 . Efim A Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady. 11, 1277\u20131280.","journal-title":"Soviet Math. Doklady."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12142"},{"key":"e_1_3_2_1_32_1","unstructured":"Jack Edmonds. 1970. Submodular functions matroids and certain polyhedra. In Combinatorial structures and their applications. Gordon and Breach 69\u201387. \t\t\t\t Jack Edmonds. 1970. Submodular functions matroids and certain polyhedra. In Combinatorial structures and their applications. Gordon and Breach 69\u201387."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Jack Edmonds GB Dantzig AF Veinott and M J\u00fcnger. 1968. Matroid partition. 50 Years of Integer Programming 1958\u20132008 199. \t\t\t\t Jack Edmonds GB Dantzig AF Veinott and M J\u00fcnger. 1968. Matroid partition. 50 Years of Integer Programming 1958\u20132008 199.","DOI":"10.1007\/978-3-540-68279-0_7"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069b.016"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218008"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62252"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103436"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015746"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.14"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63463"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"e_1_3_2_1_45_1","unstructured":"Martin Gardner. 1961. The Second Scientific American Book of Mathematical Puzzles and Diversions. 86\u201386 pages. \t\t\t\t Martin Gardner. 1961. The Second Scientific American Book of Mathematical Puzzles and Diversions. 86\u201386 pages."},{"key":"e_1_3_2_1_46_1","volume-title":"Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs\/1509.06464","author":"Gibb David","year":"2015","unstructured":"David Gibb , Bruce M. Kapron , Valerie King , and Nolan Thorn . 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs\/1509.06464 ( 2015 ), arXiv:1509.06464. arxiv:1509.06464 David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs\/1509.06464 (2015), arXiv:1509.06464. arxiv:1509.06464"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Jack E Graver Brigitte Servatius and Herman Servatius. 1993. Combinatorial rigidity. American Mathematical Soc.. \t\t\t\t Jack E Graver Brigitte Servatius and Herman Servatius. 1993. Combinatorial rigidity. American Mathematical Soc..","DOI":"10.1090\/gsm\/002"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62228"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467908"},{"volume-title":"Matroid intersection, pointer chasing, and Young\u2019s seminormal representation of S_ n","author":"Harvey Nicholas J. A.","key":"e_1_3_2_1_50_1","unstructured":"Nicholas J. A. Harvey . 2008. Matroid intersection, pointer chasing, and Young\u2019s seminormal representation of S_ n . In SODA. SIAM , 542\u2013549. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347142 Nicholas J. A. Harvey. 2008. Matroid intersection, pointer chasing, and Young\u2019s seminormal representation of S_ n. In SODA. SIAM, 542\u2013549. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347142"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684008"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384284"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585865"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681329"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.15"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.59"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00017"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00111"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461806"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-25.1.55"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_72_1","volume-title":"A note on Cunningham\u2019s algorithm for matroid intersection. CoRR, abs\/1904.04129","author":"Nguyen Huy L.","year":"2019","unstructured":"Huy L. Nguyen . 2019. A note on Cunningham\u2019s algorithm for matroid intersection. CoRR, abs\/1904.04129 ( 2019 ), arxiv:1904.04129 Huy L. Nguyen. 2019. A note on Cunningham\u2019s algorithm for matroid intersection. CoRR, abs\/1904.04129 (2019), arxiv:1904.04129"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804906"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(68)90163-7"},{"volume-title":"Combinatorial Algorithms for Submodular Function Minimization and Related Problems. Master\u2019s thesis","author":"Price Christopher","key":"e_1_3_2_1_75_1","unstructured":"Christopher Price . 2015. Combinatorial Algorithms for Submodular Function Minimization and Related Problems. Master\u2019s thesis . University of Waterloo . http:\/\/hdl.handle.net\/10012\/9356 Christopher Price. 2015. Combinatorial Algorithms for Submodular Function Minimization and Related Problems. Master\u2019s thesis. University of Waterloo. http:\/\/hdl.handle.net\/10012\/9356"},{"key":"e_1_3_2_1_76_1","volume-title":"Faster exact and approximation algorithms for packing and covering matroids via push-relabel. CoRR, abs\/2303.01478","author":"Quanrud Kent","year":"2023","unstructured":"Kent Quanrud . 2023. Faster exact and approximation algorithms for packing and covering matroids via push-relabel. CoRR, abs\/2303.01478 ( 2023 ), https:\/\/doi.org\/10.48550\/arXiv.2303.01478 arXiv:2303.01478. 10.48550\/arXiv.2303.01478 Kent Quanrud. 2023. Faster exact and approximation algorithms for packing and covering matroids via push-relabel. CoRR, abs\/2303.01478 (2023), https:\/\/doi.org\/10.48550\/arXiv.2303.01478 arXiv:2303.01478."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.701"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.39"},{"key":"e_1_3_2_1_79_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency . Springer . Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(55)90186-1"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520068"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451108"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00090"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00036"},{"volume-title":"Matroid theory","author":"Welsh Dominic JA","key":"e_1_3_2_1_86_1","unstructured":"Dominic JA Welsh . 1976. Matroid theory . Academic Press , London, New York. Dominic JA Welsh. 1976. Matroid theory. Academic Press, London, New York."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401025"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58325-4_231"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T16:39:53Z","timestamp":1698683993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":89,"alternative-id":["10.1145\/3564246.3585219","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585219","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}