{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:14:12Z","timestamp":1787498052158,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384327","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"181-193","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Near-optimal fully dynamic densest subgraph"],"prefix":"10.1145","author":[{"given":"Saurabh","family":"Sawlani","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junxing","family":"Wang","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.4"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13123-8_6"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.005"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.30"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_3_2_1_17_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Boob Digvijay","year":"2019","unstructured":"Digvijay Boob , Saurabh Sawlani , and Di Wang . 2019 . Faster width-dependent algorithm for mixed packing and covering LPs . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 15253-15262. http:\/\/papers.nips.cc\/paper\/9663-fasterwidth-dependent-algorithm-for-mixed-packing-and-covering-lps Digvijay Boob, Saurabh Sawlani, and Di Wang. 2019. Faster width-dependent algorithm for mixed packing and covering LPs. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 15253-15262. http:\/\/papers.nips.cc\/paper\/9663-fasterwidth-dependent-algorithm-for-mixed-packing-and-covering-lps"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_34"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92695-5_4"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_3_2_1_26_1","unstructured":"D. R. Ford and D. R. Fulkerson. 2010. Flows in Networks. Princeton University Press Princeton NJ USA.  D. R. Ford and D. R. Fulkerson. 2010. Flows in Networks. Princeton University Press Princeton NJ USA."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_3_2_1_32_1","unstructured":"Gramoz Goranci Monika Henzinger and Thatchaphol Saranurak. 2018. Fast Incremental Algorithms via Local Sparsifiers. ( 2018 ). unpublished manuscript.  Gramoz Goranci Monika Henzinger and Thatchaphol Saranurak. 2018. Fast Incremental Algorithms via Local Sparsifiers. ( 2018 ). unpublished manuscript."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_34_1","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science, A Min Tjoa, Ladjel Bellatreche, Stefan Bifl, Jan van Leeuwen, and Ji\u0159\u00ed Wiedermann (Eds.)","author":"Henzinger Monika","unstructured":"Monika Henzinger . 2018. The State of the Art in Dynamic Graph Algorithms . In SOFSEM 2018: Theory and Practice of Computer Science, A Min Tjoa, Ladjel Bellatreche, Stefan Bifl, Jan van Leeuwen, and Ji\u0159\u00ed Wiedermann (Eds.) . Springer International Publishing , Cham , 40-44. Monika Henzinger. 2018. The State of the Art in Dynamic Graph Algorithms. In SOFSEM 2018: Theory and Practice of Computer Science, A Min Tjoa, Ladjel Bellatreche, Stefan Bifl, Jan van Leeuwen, and Ji\u0159\u00ed Wiedermann (Eds.). Springer International Publishing, Cham, 40-44."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_3_2_1_39_1","volume-title":"Italiano and Piotr Sankowski","author":"Giuseppe","year":"2010","unstructured":"Giuseppe F. Italiano and Piotr Sankowski . 2010 . Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs. CoRR abs\/1011.2843 ( 2010 ). arXiv: 1011.2843 http:\/\/arxiv.org\/abs\/1011.2843 Giuseppe F. Italiano and Piotr Sankowski. 2010. Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs. CoRR abs\/1011.2843 ( 2010 ). arXiv: 1011.2843 http:\/\/arxiv.org\/abs\/1011.2843"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_2_1_41_1","unstructured":"Ravi Kannan and Vinay V. 1999. Analyzing the structure of large graphs. ( 1999 ). unpublished manuscript.  Ravi Kannan and Vinay V. 1999. Analyzing the structure of large graphs. ( 1999 ). unpublished manuscript."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_45"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.12.006"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129299"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Serge A Plotkin David B Shmoys and \u00c9va Tardos. 1995. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20 2 ( 1995 ) 257-301.  Serge A Plotkin David B Shmoys and \u00c9va Tardos. 1995. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20 2 ( 1995 ) 257-301.","DOI":"10.1287\/moor.20.2.257"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1186\/1752-0509-7-S4-S12"},{"key":"e_1_3_2_1_57_1","volume-title":"Research in Computational Molecular Biology","author":"Saha Barna","unstructured":"Barna Saha , Allison Hoch , Samir Khuller , Louiqa Raschid , and Xiao-Ning Zhang . 2010. Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs . In Research in Computational Molecular Biology , Bonnie Berger (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg , 456-472. Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao-Ning Zhang. 2010. Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. In Research in Computational Molecular Biology, Bonnie Berger (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 456-472."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_11"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_62_1","volume-title":"Vu","author":"Su Hsin-Hao","year":"2019","unstructured":"Hsin-Hao Su and Hoa T . Vu . 2019 . Distributed Dense Subgraph Detection and Low Outdegree Orientation. CoRR abs\/ 1907.12443 ( 2019 ). Hsin-Hao Su and Hoa T. Vu. 2019. Distributed Dense Subgraph Detection and Low Outdegree Orientation. CoRR abs\/ 1907.12443 ( 2019 )."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_16"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0045-2"},{"key":"e_1_3_2_1_65_1","unstructured":"Charalampos E. Tsourakakis. 2014. A Novel Approach to Finding NearCliques: The Triangle-Densest Subgraph Problem. CoRR abs\/1405.1477 ( 2014 ). arXiv: 1405.1477 http:\/\/arxiv.org\/abs\/1405.1477  Charalampos E. Tsourakakis. 2014. A Novel Approach to Finding NearCliques: The Triangle-Densest Subgraph Problem. CoRR abs\/1405.1477 ( 2014 ). arXiv: 1405.1477 http:\/\/arxiv.org\/abs\/1405.1477"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384327","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:57Z","timestamp":1750185177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":63,"alternative-id":["10.1145\/3357713.3384327","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384327","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}