{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:45:28Z","timestamp":1783784728622,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":61,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188922","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"815-826","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Fully dynamic maximal independent set with sublinear update time"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Onak","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017.  Ittai Abraham Shiri Chechik and Sebastian Krinninger. 2017."},{"key":"e_1_3_2_2_2_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Fully","year":"2017","unstructured":"Fully dynamic all-pairs shortest paths with worst-case update-time revisited . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain , January 16-19, 2017 . 440\u2013452. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 16-19, 2017. 440\u2013452."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_9"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.098"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_2_10_1","unstructured":"Aaron Bernstein and Liam Roditty. 2011.  Aaron Bernstein and Liam Roditty. 2011."},{"key":"e_1_3_2_2_11_1","volume-title":"Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011","author":"Improved","year":"2011","unstructured":"Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 , San Francisco, CA, USA , January 23-25, 2011 . 1355\u20131365. Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, USA, January 23-25, 2011. 1355\u20131365."},{"key":"e_1_3_2_2_12_1","unstructured":"Aaron Bernstein and Cliff Stein. 2015.  Aaron Bernstein and Cliff Stein. 2015."},{"key":"e_1_3_2_2_13_1","volume-title":"Dynamic Matching in Bipartite Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015","author":"Fully","year":"2015","unstructured":"Fully Dynamic Matching in Bipartite Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015 , Kyoto, Japan , July 6-10, 2015 , Part I. 167\u2013 179. Fully Dynamic Matching in Bipartite Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Part I. 167\u2013 179."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_2_16_1","unstructured":"Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger and Danupon Nanongkai. 2018.  Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger and Danupon Nanongkai. 2018."},{"key":"e_1_3_2_2_17_1","volume-title":"Algorithms for Graph Coloring. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Dynamic","year":"2018","unstructured":"Dynamic Algorithms for Graph Coloring. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 , New Orleans, LA, USA , January 7-10, 2018 . 1\u201320. Dynamic Algorithms for Graph Coloring. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. 1\u201320."},{"key":"e_1_3_2_2_18_1","volume-title":"Italiano","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Giuseppe F . Italiano . 2015 . Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 2015."},{"key":"e_1_3_2_2_19_1","volume-title":"Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Deterministic","year":"2015","unstructured":"Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA , January 4-6, 2015 . 785\u2013804. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. 785\u2013804."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_2_21_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Bhattacharya Sayan","year":"2017","unstructured":"Sayan Bhattacharya , Monika Henzinger , and Danupon Nanongkai . 2017 . Fully Dynamic Maximum Matching and Vertex Cover in O(log 3 n) Worst Case Update Time . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain , January 16-19, 2017. 470\u2013489. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 2017. Fully Dynamic Maximum Matching and Vertex Cover in O(log 3 n) Worst Case Update Time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 16-19, 2017. 470\u2013489."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933083"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/358141.358144"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_3_2_2_25_1","unstructured":"David Eppstein Zvi Galil Giuseppe F. Italiano and Amnon Nissenzweig. 1997.  David Eppstein Zvi Galil Giuseppe F. Italiano and Amnon Nissenzweig. 1997."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_3_2_2_30_1","unstructured":"Anupam Gupta Ravishankar Krishnaswamy Amit Kumar and Debmalya Panigrahi. 2017.  Anupam Gupta Ravishankar Krishnaswamy Amit Kumar and Debmalya Panigrahi. 2017."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_3_2_2_32_1","unstructured":"Manoj Gupta and Richard Peng. 2013.  Manoj Gupta and Richard Peng. 2013."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.24"},{"key":"e_1_3_2_2_35_1","unstructured":"Monika Henzinger Sebastian Krinninger and Danupon Nanongkai. 2014.  Monika Henzinger Sebastian Krinninger and Danupon Nanongkai. 2014."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591869"},{"key":"e_1_3_2_2_37_1","unstructured":"674\u2013683.  674\u2013683."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685829"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_2_42_1","volume-title":"Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993","author":"Ivkovi\u0107 Zoran","year":"1993","unstructured":"Zoran Ivkovi\u0107 and Errol L. Lloyd . 1993. Fully Dynamic Maintenance of Vertex Cover . In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993 , Utrecht, The Netherlands , June 16-18, 1993 . Zoran Ivkovi\u0107 and Errol L. Lloyd. 1993. Fully Dynamic Maintenance of Vertex Cover. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993, Utrecht, The Netherlands, June 16-18, 1993."},{"key":"e_1_3_2_2_43_1","unstructured":"99\u2013111.  99\u2013111."},{"key":"e_1_3_2_2_44_1","volume-title":"Karp and Avi Wigderson","author":"Richard","year":"1985","unstructured":"Richard M. Karp and Avi Wigderson . 1985 . Richard M. Karp and Avi Wigderson. 1985."},{"key":"e_1_3_2_2_45_1","volume-title":"762\u2013773","author":"Maximal Independent Set Problem A Fast Parallel","year":"1985","unstructured":"A Fast Parallel Algorithm for the Maximal Independent Set Problem . J. ACM 32, 4 ( 1985 ), 762\u2013773 . A Fast Parallel Algorithm for the Maximal Independent Set Problem. J. ACM 32, 4 (1985), 762\u2013773."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_2_51_1","unstructured":"Alessandro Panconesi and Aravind Srinivasan. 1996.  Alessandro Panconesi and Aravind Srinivasan. 1996."},{"key":"e_1_3_2_2_52_1","volume-title":"Algorithms 20, 2","author":"Distributed Network Decomposition On","year":"1996","unstructured":"On the Complexity of Distributed Network Decomposition . J. Algorithms 20, 2 ( 1996 ), 356\u2013374. On the Complexity of Distributed Network Decomposition. J. Algorithms 20, 2 (1996), 356\u2013374."},{"key":"e_1_3_2_2_53_1","unstructured":"Merav Parter David Peleg and Shay Solomon. 2016.  Merav Parter David Peleg and Shay Solomon. 2016."},{"key":"e_1_3_2_2_54_1","volume-title":"Distributed Tasks. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","year":"2016","unstructured":"Local-on-Average Distributed Tasks. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 , Arlington, VA, USA , January 10-12, 2016 . 220\u2013 239. Local-on-Average Distributed Tasks. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 220\u2013 239."},{"key":"e_1_3_2_2_55_1","unstructured":"David Peleg. 2000.  David Peleg. 2000."},{"key":"e_1_3_2_2_56_1","volume-title":"A Locality-Sensitive Approach","author":"Computing Distributed","unstructured":"Distributed Computing : A Locality-Sensitive Approach . Society for Industrial and Applied Mathematics (SIAM) . Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics (SIAM)."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060607"},{"key":"e_1_3_2_2_60_1","unstructured":"Christian Wulff-Nilsen. 2017.  Christian Wulff-Nilsen. 2017."},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3188922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188922","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.3188922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":61,"alternative-id":["10.1145\/3188745.3188922","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188922","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"}}]}}