{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T04:13:51Z","timestamp":1780546431691,"version":"3.54.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,11,16]],"date-time":"2015-11-16T00:00:00Z","timestamp":1447632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["523\/12"],"award-info":[{"award-number":["523\/12"]}]},{"name":"ISF","award":["87209011"],"award-info":[{"award-number":["87209011"]}]},{"name":"Koshland Center for Basic Research"},{"name":"BSF","award":["2008430"],"award-info":[{"award-number":["2008430"]}]},{"name":"European Union's Seventh Framework Programme","award":["n\u00b0303809"],"award-info":[{"award-number":["n\u00b0303809"]}]},{"name":"Clore Fellowship","award":["81265410"],"award-info":[{"award-number":["81265410"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,8]]},"abstract":"\n A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges)\n n<\/jats:italic>\n -vertex graphs using a trivial deterministic algorithm with a worst-case update time of\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ). No deterministic algorithm that outperforms the na\u00efve\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) one was reported up to this date. The only progress in this direction is due to Ivkovi\u0107 and Lloyd, who in 1993 devised a deterministic algorithm with an\n amortized<\/jats:italic>\n update time of\n O<\/jats:italic>\n ((\n n<\/jats:italic>\n +\n m<\/jats:italic>\n )\n \u221a2\/2<\/jats:sup>\n ), where\n m<\/jats:italic>\n is the number of edges.\n <\/jats:p>\n \n In this article, we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of\n O<\/jats:italic>\n (\u221a\n m<\/jats:italic>\n ). Moreover, our algorithm maintains a matching, which in fact is a 3\/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 \u2212 \u03f5)-approximate MCM improving upon the na\u00efve\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) was known prior to this work, even allowing amortized time bounds and randomization.\n <\/jats:p>\n \n For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sublogarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of\n O<\/jats:italic>\n (log\u2009\n n<\/jats:italic>\n \/log\u2009log\u2009\n n<\/jats:italic>\n ). This result addresses an open question of Onak and Rubinfeld [2010].\n <\/jats:p>\n \n We also show a deterministic algorithm with optimal space usage, which for arbitrary graphs maintains a maximal matching in amortized\n O<\/jats:italic>\n (\u221a\n m<\/jats:italic>\n ) time and uses only\n O<\/jats:italic>\n (\n n<\/jats:italic>\n +\n m<\/jats:italic>\n ) space.\n <\/jats:p>","DOI":"10.1145\/2700206","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Simple Deterministic Algorithms for Fully Dynamic Maximal Matching"],"prefix":"10.1145","volume":"12","author":[{"given":"Ofer","family":"Neiman","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"A. Aho J. Hopcroft and J. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. A. Aho J. Hopcroft and J. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of SODA. 312--321","author":"Alberts D."},{"key":"e_1_2_1_3_1","unstructured":"A. Anand. 2012. (2012). Personal communication. A. Anand. 2012. (2012). Personal communication."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195238"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of WADS. 342--351","author":"Brodal G. S."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90100-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059514"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of WG. 99--111","author":"Ivkovi\u0107 Z."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1883"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Decomposition of finite graphs into forests","volume":"39","author":"Nash-Williams C.","year":"1964","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of SODA. 118--126","author":"Sankowski P.","year":"2007"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0045-2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:43Z","timestamp":1750223263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,16]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,8]]}},"alternative-id":["10.1145\/2700206"],"URL":"https:\/\/doi.org\/10.1145\/2700206","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,16]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}