{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:59Z","timestamp":1750220759982,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"IBM Herman Goldstine Postdoctoral Fellowship"},{"name":"NSF Graduate Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            We consider the problem of maintaining a maximal independent set in a dynamic graph subject to edge insertions and deletions. Recently, Assadi et al. (at STOC\u201918) showed that a maximal independent set can be maintained in\n            <jats:italic>sublinear<\/jats:italic>\n            (in the dynamically changing number of edges) amortized update time. In this article, we significantly improve the update time for\n            <jats:italic>uniformly sparse graphs<\/jats:italic>\n            . Specifically, for graphs with arboricity \u03b1, the amortized update time of our algorithm is\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\n            <jats:sup>2<\/jats:sup>\n            \u22c5 log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs and some classes of \u201creal-world\u201d graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>3\/8\u2212\u03f5<\/jats:sup>\n            , for any constant \u03f5 &gt; 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/3378025","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully Dynamic MIS in Uniformly Sparse Graphs"],"prefix":"10.1145","volume":"16","author":[{"given":"Krzysztof","family":"Onak","sequence":"first","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology, University Heights, Newark, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Wein","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.116"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917)","author":"Berglin Edvin","year":"2017","unstructured":"Edvin Berglin and Gerth St\u00f8lting Brodal . 2017 . A simple greedy algorithm for dynamic graph orientation . In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917) . Article 12, 12 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC. 2017.12 10.4230\/LIPIcs.ISAAC.2017.12 Edvin Berglin and Gerth St\u00f8lting Brodal. 2017. A simple greedy algorithm for dynamic graph orientation. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917). Article 12, 12 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.12"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645932.673191"},{"volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977)","author":"Carter Larry","key":"e_1_2_1_8_1","unstructured":"Larry Carter and Mark N. Wegman . 1977. Universal classes of hash functions . In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977) . 106--112. Larry Carter and Mark N. Wegman. 1977. Universal classes of hash functions. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977). 106--112."},{"volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Censor-Hillel Keren","key":"e_1_2_1_9_1","unstructured":"Keren Censor-Hillel , Elad Haramaty , and Zohar S. Karnin . 2016. Optimal dynamic distributed MIS . In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916) . 217--226. DOI:https:\/\/doi.org\/10.1145\/2933057.2933083 10.1145\/2933057.2933083 Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. 2016. Optimal dynamic distributed MIS. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916). 217--226. DOI:https:\/\/doi.org\/10.1145\/2933057.2933083"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201912)","author":"Daum Sebastian","key":"e_1_2_1_11_1","unstructured":"Sebastian Daum , Seth Gilbert , Fabian Kuhn , and Calvin C. Newport . 2012. Leader election in shared spectrum radio networks . In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201912) . 215--224. DOI:https:\/\/doi.org\/10.1145\/2332432.2332470 10.1145\/2332432.2332470 Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport. 2012. Leader election in shared spectrum radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201912). 215--224. DOI:https:\/\/doi.org\/10.1145\/2332432.2332470"},{"key":"e_1_2_1_12_1","unstructured":"Yuhao Du and Hengjie Zhang. 2018. Improved algorithms for fully dynamic maximal independent set. arXiv:1804.08908.  Yuhao Du and Hengjie Zhang. 2018. Improved algorithms for fully dynamic maximal independent set. arXiv:1804.08908."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.140"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_15"},{"key":"e_1_2_1_15_1","unstructured":"Manoj Gupta and Shahbaz Khan. 2018. Simple dynamic algorithms for maximal independent set and other problems. arXiv:1804.01823.  Manoj Gupta and Shahbaz Khan. 2018. Simple dynamic algorithms for maximal independent set and other problems. arXiv:1804.01823."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13075-0_11"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"volume-title":"Proceedings of the 26th International Symposium on Distributed Computing (DISC\u201912)","author":"Jurdzinski Tomasz","key":"e_1_2_1_18_1","unstructured":"Tomasz Jurdzinski and Dariusz R. Kowalski . 2012. Distributed backbone structure for algorithms in the SINR model of wireless networks . In Proceedings of the 26th International Symposium on Distributed Computing (DISC\u201912) . 106--120. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33651-5_8 10.1007\/978-3-642-33651-5_8 Tomasz Jurdzinski and Dariusz R. Kowalski. 2012. Distributed backbone structure for algorithms in the SINR model of wireless networks. In Proceedings of the 26th International Symposium on Distributed Computing (DISC\u201912). 106--120. DOI:https:\/\/doi.org\/10.1007\/978-3-642-33651-5_8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_45"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.12.006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780565"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023720.1023746"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Huy","year":"2008","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements . In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908) . 327--336. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2008 .81 10.1109\/FOCS.2008.81 Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908). 327--336. DOI:https:\/\/doi.org\/10.1109\/FOCS.2008.81"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.016"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3378025","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3378025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:00Z","timestamp":1750200060000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3378025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3378025"],"URL":"https:\/\/doi.org\/10.1145\/3378025","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}