{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:18:53Z","timestamp":1779175133395,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of Zurich, CanDoc Grant","award":["FK-23-021"],"award-info":[{"award-number":["FK-23-021"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>During the past decades significant efforts have been made to propose data structures for answering connectivity queries on fully dynamic graphs, i.e., graphs with frequent insertions and deletions of edges. However, a comprehensive understanding of how these data structures perform in practice is missing, since not all of them have been implemented, let alone evaluated experimentally. We provide reference implementations for the proposed data structures and experimentally evaluate them on a wide range of graphs. Our findings show that the current solutions are not ready to be deployed in systems as is, as every data structure has critical weaknesses when used in practice. Key limitations that must be overcome are the space and time overhead incurred by balanced data structures, the degeneration of the runtime of space-efficient data structures in worst case scenarios, and the maintenance costs for balanced data structures. We detail our findings in the experimental evaluation and provide recommendations for implementing robust solutions for answering connectivity queries on dynamic graphs.<\/jats:p>","DOI":"10.1145\/3709660","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0811-0752","authenticated-orcid":false,"given":"Qing","family":"Chen","sequence":"first","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3694-9026","authenticated-orcid":false,"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9666-1932","authenticated-orcid":false,"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Network Diameter. Retrieved","year":"2024","unstructured":"2024. Network Diameter. Retrieved May 24, 2024 from http:\/\/konect.cc\/statistics\/diam\/"},{"key":"e_1_2_2_2_1","unstructured":"2024. NetworkX. Retrieved March 24 2024 from https:\/\/networkx.org\/"},{"key":"e_1_2_2_3_1","volume-title":"NetworkX: complete graph. Retrieved","year":"2024","unstructured":"2024. NetworkX: complete graph. Retrieved January 9, 2024 from https:\/\/networkx.org\/documentation\/stable\/reference\/generated\/networkx.generators.classic.complete_graph.html"},{"key":"e_1_2_2_4_1","volume-title":"NetworkX: gnm random graph. Retrieved","year":"2024","unstructured":"2024. NetworkX: gnm random graph. Retrieved January 9, 2024 from https:\/\/networkx.org\/documentation\/stable\/reference\/generated\/networkx.generators.random_graphs.gnm_random_graph.html"},{"key":"e_1_2_2_5_1","volume-title":"NetworkX: path graph. Retrieved","year":"2024","unstructured":"2024. NetworkX: path graph. Retrieved January 9, 2024 from https:\/\/networkx.org\/documentation\/stable\/reference\/generated\/networkx.generators.classic.path_graph.html"},{"key":"e_1_2_2_6_1","volume-title":"NetworkX: power law graph. Retrieved","year":"2024","unstructured":"2024. NetworkX: power law graph. Retrieved January 9, 2024 from https:\/\/networkx.org\/documentation\/stable\/reference\/generated\/networkx.generators.random_graphs.powerlaw_cluster_graph.html"},{"key":"e_1_2_2_7_1","volume-title":"NetworkX: star graph. Retrieved","year":"2024","unstructured":"2024. NetworkX: star graph. Retrieved January 9, 2024 from https:\/\/networkx.org\/documentation\/stable\/reference\/generated\/networkx.generators.classic.star_graph.html"},{"key":"e_1_2_2_8_1","volume-title":"Retrieved","year":"2024","unstructured":"2024. Road networks for full USA. Retrieved January 22, 2024 from http:\/\/konect.cc\/networks\/dimacs9-USA\/"},{"key":"e_1_2_2_9_1","volume-title":"Retrieved","year":"2024","unstructured":"2024. SNAP: Stack Overflow temporal network. Retrieved January 22, 2024 from http:\/\/snap.stanford.edu\/data\/sxstackoverflow.html"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","unstructured":"David Alberts. 1995. Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King. http:\/\/dx.doi.org\/10.17169\/refubium-21860.","DOI":"10.17169\/refubium-21860"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"key":"e_1_2_2_12_1","volume-title":"Sam Skjonsberg, Lucy Lu Wang, Chris Wilhelm, Zheng Yuan, Madeleine van Zuylen, and Oren Etzioni.","author":"Ammar Waleed","year":"2018","unstructured":"Waleed Ammar, Dirk Groeneveld, Chandra Bhagavatula, Iz Beltagy, Miles Crawford, Doug Downey, Jason Dunkelberger, Ahmed Elgohary, Sergey Feldman, Vu Ha, Rodney Kinney, Sebastian Kohlmeier, Kyle Lo, Tyler Murray, Hsu-Han Ooi, Matthew Peters, Joanna Power, Sam Skjonsberg, Lucy Lu Wang, Chris Wilhelm, Zheng Yuan, Madeleine van Zuylen, and Oren Etzioni. 2018. Construction of the Literature Graph in Semantic Scholar. In NAACL. https:\/\/www.semanticscholar.org\/paper\/09e3cf5704bcb16e6657f6ceed70e93373a54618"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447905"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01864-0"},{"key":"e_1_2_2_15_1","unstructured":"Qing Chen Michael H. B\u00f6hlen and Sven Helmer. 2025. An experimental comparison of tree-data structures for connectivity queries on fully-dynamic undirected graphs (Extended Version). arXiv:2501.02278 https:\/\/arxiv.org\/abs\/ 2501.02278"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457270"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267818"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167159"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3500930"},{"key":"e_1_2_2_21_1","unstructured":"Xiyang Feng Guodong Jin Ziyi Chen Chang Liu and Semih Saliholu. 2023. K\u00f9zu Graph Database Management System. In CIDR."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514065"},{"key":"e_1_2_2_23_1","volume-title":"Algorithmic graph theory","author":"Gibbons Alan","unstructured":"Alan Gibbons. 1985. Algorithmic graph theory. Cambridge university press."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAS.1980.319631"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555806"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009228"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280036"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.32"},{"key":"e_1_2_2_33_1","volume-title":"Fully Dynamic Connectivity in (log(log log)2 ) Amortized Expected Time. TheoretiCS 2","author":"Huang Shang-En","year":"2023","unstructured":"Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. 2023. Fully Dynamic Connectivity in (log(log log)2 ) Amortized Expected Time. TheoretiCS 2 (2023)."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945398"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/DRPT.2008.4523877"},{"key":"e_1_2_2_38_1","unstructured":"Alan Mislove. 2009. Online Social Networks: Measurement Analysis and Applications to Distributed Information Systems. Ph.D. Dissertation. Rice University Department of Computer Science."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.59"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232535"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802464"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654960"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_2_2_50_1","unstructured":"Douglas Brent West et al. 2001. Introduction to graph theory. Vol. 2. Prentice hall Upper Saddle River."},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1757--1769","year":"2013","unstructured":"ChristianWulff-Nilsen. 2013. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1757--1769."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675040"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:19:43Z","timestamp":1774981183000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709660"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709660"],"URL":"https:\/\/doi.org\/10.1145\/3709660","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}