{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T11:13:34Z","timestamp":1770549214420,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>\n            Answering connectivity queries is fundamental to fully dynamic graphs where edges and vertices are inserted and deleted frequently. Existing work proposes data structures and algorithms with worst case guarantees. We propose a new data structure, the\n            <jats:italic>dynamic tree<\/jats:italic>\n            (D-tree), together with algorithms to construct and maintain it. The D-tree is the first data structure that scales to fully dynamic graphs with millions of vertices and edges and, on average, answers connectivity queries much faster than data structures with worst case guarantees.\n          <\/jats:p>","DOI":"10.14778\/3551793.3551868","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3263-3276","source":"Crossref","is-referenced-by-count":11,"title":["Dynamic spanning trees for connectivity queries on fully-dynamic undirected graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Qing","family":"Chen","sequence":"first","affiliation":[{"name":"University of Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Lachish","sequence":"additional","affiliation":[{"name":"University of London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[{"name":"University of Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[{"name":"University of Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2021","unstructured":"2021. SNAP : Stack Overflow temporal network . Retrieved October 21, 2021 from http:\/\/snap.stanford.edu\/data\/sx-stackoverflow.html 2021. SNAP: Stack Overflow temporal network. Retrieved October 21, 2021 from http:\/\/snap.stanford.edu\/data\/sx-stackoverflow.html"},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","year":"2022","unstructured":"2022. KONECT : The KONECT Project . Retrieved June 02, 2022 from http:\/\/konect.cc\/statistics\/diam\/ 2022. KONECT: The KONECT Project. Retrieved June 02, 2022 from http:\/\/konect.cc\/statistics\/diam\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"key":"e_1_2_1_4_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 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_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_6_1","volume-title":"B\u00f6hlen","author":"Chen Qing","year":"2022","unstructured":"Qing Chen , Oded Lachish , Sven Helmer , and Michael H . B\u00f6hlen . 2022 . Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version). Technical report. CoRR ( 2022). https:\/\/arxiv.org\/pdf\/2207.06887.pdf Qing Chen, Oded Lachish, Sven Helmer, and Michael H. B\u00f6hlen. 2022. Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version). Technical report. CoRR (2022). https:\/\/arxiv.org\/pdf\/2207.06887.pdf"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90022-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545503"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen , Charles E Leiserson , Ronald L Rivest , and Clifford Stein . 2009. Introduction to algorithms . MIT press . Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010767517079"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.12.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267818"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11557067_33"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808754"},{"key":"e_1_2_1_17_1","volume-title":"Algorithmic graph theory","author":"Gibbons Alan","unstructured":"Alan Gibbons . 1985. Algorithmic graph theory . Cambridge university press . Alan Gibbons. 1985. Algorithmic graph theory. Cambridge university press."},{"key":"e_1_2_1_18_1","volume-title":"Survey of Graph Analysis Applications. CoRR abs\/1807.00382","author":"Hegeman Tim","year":"2018","unstructured":"Tim Hegeman and Alexandru Iosup . 2018. Survey of Graph Analysis Applications. CoRR abs\/1807.00382 ( 2018 ). arXiv:1807.00382 http:\/\/arxiv.org\/abs\/1807.00382 Tim Hegeman and Alexandru Iosup. 2018. Survey of Graph Analysis Applications. CoRR abs\/1807.00382 (2018). arXiv:1807.00382 http:\/\/arxiv.org\/abs\/1807.00382"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39737-3_28"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63165-8214"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009268"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039718"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945398"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.53"},{"key":"e_1_2_1_33_1","volume-title":"DBL: Efficient Reachability Queries on Dynamic Graphs. In International Conference on Database Systems for Advanced Applications. Springer, 761--777","author":"Lyu Qiuyi","year":"2021","unstructured":"Qiuyi Lyu , Yuchen Li , Bingsheng He , and Bin Gong . 2021 . DBL: Efficient Reachability Queries on Dynamic Graphs. In International Conference on Database Systems for Advanced Applications. Springer, 761--777 . Qiuyi Lyu, Yuchen Li, Bingsheng He, and Bin Gong. 2021. DBL: Efficient Reachability Queries on Dynamic Graphs. In International Conference on Database Systems for Advanced Applications. Springer, 761--777."},{"key":"e_1_2_1_35_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K . Ahmed . 2015 . The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. http:\/\/networkrepository.com Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. http:\/\/networkrepository.com"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434642"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204032"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/96559.214080"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Robert Endre Tarjan. 1983. Data structures and network algorithms. SIAM.  Robert Endre Tarjan. 1983. Data structures and network algorithms. SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715896"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_2_1_48_1","unstructured":"Douglas Brent West etal 2001. Introduction to graph theory. Vol. 2. Prentice hall Upper Saddle River.  Douglas Brent West et al. 2001. Introduction to graph theory. Vol. 2. Prentice hall Upper Saddle River."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.126"},{"key":"e_1_2_1_50_1","volume-title":"Implementations and Experimental Studies of Dynamic Graph Algorithms","author":"Zaroliagis Christos D.","unstructured":"Christos D. Zaroliagis . 2002. Implementations and Experimental Studies of Dynamic Graph Algorithms . Springer-Verlag , Berlin, Heidelberg , 2290--278. Christos D. Zaroliagis. 2002. Implementations and Experimental Studies of Dynamic Graph Algorithms. Springer-Verlag, Berlin, Heidelberg, 2290--278."},{"key":"e_1_2_1_51_1","first-page":"87","article-title":"Medians and Peripherians of Trees","volume":"4","author":"Zelinka Bohdan","year":"1968","unstructured":"Bohdan Zelinka . 1968 . Medians and Peripherians of Trees . Archivum Mathematicum 4 , 2 (1968), 87 -- 95 . Bohdan Zelinka. 1968. Medians and Peripherians of Trees. Archivum Mathematicum 4, 2 (1968), 87--95.","journal-title":"Archivum Mathematicum"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:57:18Z","timestamp":1672225038000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":51,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551868"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551868","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}