{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:22Z","timestamp":1750220902013,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100017248","name":"Open University of Israel","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100017248","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ISF","award":["724\/15"],"award-info":[{"award-number":["724\/15"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            We study dynamic graphs in the fully dynamic\n            <jats:italic>centralized<\/jats:italic>\n            setting. In this setting, the vertex set of size\n            <jats:italic>n<\/jats:italic>\n            of a graph\n            <jats:italic>G<\/jats:italic>\n            is fixed, and the edge set changes step-by-step, such that each step either adds or removes an edge. Dynamic graphs have various applications in fields such as Communication Networks, Computer Graphics, and VLSI Design. The goal in this setting is maintaining a solution to a certain problem (e.g., maximal matching, edge coloring) after each step, such that each step is executed efficiently. The running time of a step is called\n            <jats:italic>update-time<\/jats:italic>\n            . One can think of this setting as a dynamic network that is monitored by a central processor that is responsible for maintaining the solution. Prior to the current work, for several central problems, the best-known deterministic algorithms for general graphs were the naive ones with update-time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). This is the case for maximal matching and proper\n            <jats:italic>O<\/jats:italic>\n            (\u0394)-edge-coloring. The question of existence of sublinear in\n            <jats:italic>n<\/jats:italic>\n            update-time deterministic algorithms for dense graphs and general graphs remained wide open. In this article, we address this question by devising sublinear update-time deterministic algorithms for maximal matching in\n            <jats:italic>graphs with bounded neighborhood independence<\/jats:italic>\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/ log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), and for proper\n            <jats:italic>O<\/jats:italic>\n            (\u0394)-edge-coloring in\n            <jats:italic>general graphs<\/jats:italic>\n            . The family of graphs with bounded neighborhood independence is a very wide family of dense graphs. In particular, graphs with constant neighborhood independence include line-graphs, claw-free graphs, unit disk graphs, and many other graphs. Thus, these graphs represent very well various types of networks. For graphs with constant neighborhood independence, our maximal-matching algorithm has \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            ) update-time. Our\n            <jats:italic>O<\/jats:italic>\n            (\u0394)-edge-coloring algorithms has \u00d5(\u221a \u0394 ) update-time for general graphs.\n          <\/jats:p>\n          <jats:p>To obtain our results, we employ a novel approach that adapts certain distributed algorithms of the LOCAL setting to the centralized fully dynamic setting. This is achieved by optimizing the work each processor performs and efficiently simulating a distributed algorithm in a centralized setting. The simulation is efficient, thanks to a careful selection of the network parts that the algorithm is invoked on, and by deducing the solution from the additional information that is present in the centralized setting, but not in the distributed one. Our experiments on various network topologies and scenarios demonstrate that our algorithms are highly efficient in practice. We believe that our approach is of independent interest and may be applicable to additional problems.<\/jats:p>","DOI":"10.1145\/3338529","type":"journal-article","created":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T12:14:48Z","timestamp":1567685688000},"page":"1-24","source":"Crossref","is-referenced-by-count":3,"title":["Fully Dynamic Graph Algorithms Inspired by Distributed Computing"],"prefix":"10.1145","volume":"24","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[{"name":"Open University of Israel, Raanana, Israel"}]},{"given":"Tzalik","family":"Maimon","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}]}],"member":"320","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Congress. Num. 47","author":"Andrews J.","year":"1985","unstructured":"J. Andrews and M. Jacobson . 1985. On a generalization of a chromatic number . Congress. Num. 47 ( 1985 ), 331--48. J. Andrews and M. Jacobson. 1985. On a generalization of a chromatic number. Congress. Num. 47 (1985), 331--48."},{"volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1345--1364","author":"Assadi S.","key":"e_1_2_1_2_1","unstructured":"S. Assadi , S. Khanna , Y. Li , and G. Yaroslavtsev . 2016. Maximum matchings in dynamic graph streams and the simultaneous communication model . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1345--1364 . S. Assadi, S. Khanna, Y. Li, and G. Yaroslavtsev. 2016. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1345--1364."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"volume-title":"Proceedings of the 15th International Symposium on Algorithms and Data Structures. 97--108","author":"Barba L.","key":"e_1_2_1_4_1","unstructured":"L. Barba , J. Cardinal , M. Korman , S. Langerman , A. Renssen , M. Roeloffzen , and S. Verdonschot . 2017. Dynamic graph coloring . In Proceedings of the 15th International Symposium on Algorithms and Data Structures. 97--108 . L. Barba, J. Cardinal, M. Korman, S. Langerman, A. Renssen, M. Roeloffzen, and S. Verdonschot. 2017. Dynamic graph coloring. In Proceedings of the 15th International Symposium on Algorithms and Data Structures. 97--108."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835797"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993825"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"volume-title":"Proceedings of the 17th International Conference on Computational Sciences. 89--98","author":"Barenboim L.","key":"e_1_2_1_9_1","unstructured":"L. Barenboim and T. Maimon . 2017. Fully dynamic graph algorithms with sublinear time inspired by distributed computing . In Proceedings of the 17th International Conference on Computational Sciences. 89--98 . L. Barenboim and T. Maimon. 2017. Fully dynamic graph algorithms with sublinear time inspired by distributed computing. In Proceedings of the 17th International Conference on Computational Sciences. 89--98."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"volume-title":"Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms. 1--20","author":"Bhattacharya S.","key":"e_1_2_1_11_1","unstructured":"S. Bhattacharya , D. Chakrabarty , M. Henzinger , and D. Nanongkai . 2018. Dynamic algorithms for graph coloring . In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms. 1--20 . S. Bhattacharya, D. Chakrabarty, M. Henzinger, and D. Nanongkai. 2018. Dynamic algorithms for graph coloring. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms. 1--20."},{"volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. 785--804","author":"Bhattacharya S.","key":"e_1_2_1_12_1","unstructured":"S. Bhattacharya , M. Henzinger , and G. Italiano . 2015. Deterministic fully dynamic data structures for vertex cover and matching . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. 785--804 . S. Bhattacharya, M. Henzinger, and G. Italiano. 2015. Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. 785--804."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (Part 1), 167--179","author":"Bernstein A.","key":"e_1_2_1_14_1","unstructured":"A. Bernstein and C. Stein . 2015. Fully dynamic matching in bipartite graphs . In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (Part 1), 167--179 . A. Bernstein and C. Stein. 2015. Fully dynamic matching in bipartite graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (Part 1), 167--179."},{"volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 692--711","author":"Bernstein A.","key":"e_1_2_1_15_1","unstructured":"A. Bernstein and C. Stein . 2016. Faster fully dynamic matchings with small approximation ratios . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 692--711 . A. Bernstein and C. Stein. 2016. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 692--711."},{"volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1326--1344","author":"Chitnis R.","key":"e_1_2_1_16_1","unstructured":"R. Chitnis , G. Cormode , H. Esfandiari , M. Hajiaghayi , A. McGregor , M. Monemizadeh , and S. Vorotnikova . 2016. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1326--1344 . R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, and S. Vorotnikova. 2016. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 1326--1344."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100207"},{"volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. 548--557","author":"Cowen L.","key":"e_1_2_1_18_1","unstructured":"L. Cowen , W. Goddard , and C. Jesurum . 1997. Coloring with defect . In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. 548--557 . L. Cowen, W. Goddard, and C. Jesurum. 1997. Coloring with defect. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. 548--557."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70374-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_2_1_23_1","volume-title":"Congress. Num. 50","author":"Harary F.","year":"1985","unstructured":"F. Harary and K. Jones . 1985. Conditional colorability II: Bipartite variations . Congress. Num. 50 ( 1985 ), 205--218. F. Harary and K. Jones. 1985. Conditional colorability II: Bipartite variations. Congress. Num. 50 (1985), 205--218."},{"volume-title":"Proceedings of the 10th European Symposium on Algorithms. 538--549","author":"Haxell P.","key":"e_1_2_1_24_1","unstructured":"P. Haxell , A. Rasala , G. Wilfong , and P. Winkler . 2002. Wide-sense nonblocking WDM cross-connects . In Proceedings of the 10th European Symposium on Algorithms. 538--549 . P. Haxell, A. Rasala, G. Wilfong, and P. Winkler. 2002. Wide-sense nonblocking WDM cross-connects. In Proceedings of the 10th European Symposium on Algorithms. 538--549."},{"volume-title":"Proceedings of the 25th International Symposium on Algorithms and Computation. 128--140","author":"He M.","key":"e_1_2_1_25_1","unstructured":"M. He , G. Tang , and N. Zeh . 2014. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries . In Proceedings of the 25th International Symposium on Algorithms and Computation. 128--140 . M. He, G. Tang, and N. Zeh. 2014. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In Proceedings of the 25th International Symposium on Algorithms and Computation. 128--140."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"volume-title":"Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science. 99--111","author":"Ivkovi\u0107 Z.","key":"e_1_2_1_28_1","unstructured":"Z. Ivkovi\u0107 and E. L. Lloyd . 1993. Fully dynamic maintenance of vertex cover . In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science. 99--111 . Z. Ivkovi\u0107 and E. L. Lloyd. 1993. Fully dynamic maintenance of vertex cover. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science. 99--111."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_14"},{"volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (part 2), 532--543","author":"Kopelowitz T.","key":"e_1_2_1_30_1","unstructured":"T. Kopelowitz , R. Krauthgamer , E. Porat , and S. Solomon . 2014. Orienting fully dynamic graphs with worst-case time bounds . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (part 2), 532--543 . T. Kopelowitz, R. Krauthgamer, E. Porat, and S. Solomon. 2014. Orienting fully dynamic graphs with worst-case time bounds. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (part 2), 532--543."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 712--729","author":"Peleg D.","key":"e_1_2_1_34_1","unstructured":"D. Peleg and S. Solomon . 2016. Dynamic (1 + \u03b5)-approximate matchings: A density-sensitive approach . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 712--729 . D. Peleg and S. Solomon. 2016. Dynamic (1 + \u03b5)-approximate matchings: A density-sensitive approach. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms. 712--729."},{"volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Rossi R.","key":"e_1_2_1_35_1","unstructured":"R. Rossi and N. Ahmed . 2015. The network data repository with interactive graph analytics and visualization . Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915) . Retrieved from: http:\/\/networkrepository.com. R. Rossi and N. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915). Retrieved from: http:\/\/networkrepository.com."},{"key":"e_1_2_1_36_1","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing V. G.","year":"1964","unstructured":"V. G. Vizing . 1964 . On an estimate of the chromatic class of a p-graph . Diskret Analiz 3 (1964), 25 -- 30 . V. G. Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret Analiz 3 (1964), 25--30.","journal-title":"Diskret Analiz"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"volume-title":"Proceedings of the 26th European Symposium on Algorithms. 72:1--72:16","author":"Solomon S.","key":"e_1_2_1_38_1","unstructured":"S. Solomon and N. Wein . 2018. Improved dynamic graph coloring . In Proceedings of the 26th European Symposium on Algorithms. 72:1--72:16 . S. Solomon and N. Wein. 2018. Improved dynamic graph coloring. In Proceedings of the 26th European Symposium on Algorithms. 72:1--72:16."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338529","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3338529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:46Z","timestamp":1750203886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338529"}},"subtitle":["Deterministic Maximal Matching and Edge Coloring in Sublinear Update-Time"],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":38,"alternative-id":["10.1145\/3338529"],"URL":"https:\/\/doi.org\/10.1145\/3338529","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,9,5]]}}}