{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:19:21Z","timestamp":1779175161422,"version":"3.51.4"},"reference-count":44,"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Minimum Spanning Tree (MST) is a fundamental structure in graph analytics and can be applied in various applications. The problem of maintaining MSTs in dynamic graphs is significant, as many real-world graphs are frequently updated. Existing studies on MST maintenance primarily focus on theoretical analysis and lack practical efficiency. In this paper, we propose a novel algorithm to maintain MST in dynamic graphs, which achieves high practical efficiency. In addition to the tree structure, our main idea is to maintain a replacement edge for each tree edge. In this way, the tree structure can be immediately updated when a tree edge is deleted. We propose algorithms to maintain the replacement edge for each tree edge by sharing the computation cost in the updating process. Our performance studies on large datasets demonstrate considerable improvements over state-of-the-art solutions.<\/jats:p>","DOI":"10.1145\/3709704","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Spanning Tree Maintenance in Dynamic Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9846-8629","authenticated-orcid":false,"given":"Lantian","family":"Xu","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Sydney, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0903-1503","authenticated-orcid":false,"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Ronghua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8427-6180","authenticated-orcid":false,"given":"Yang","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_2_1_2_1","first-page":"09","article-title":"A minimum spanning tree approach of solving a transportation problem","volume":"5","author":"Akpan NP","year":"2017","unstructured":"NP Akpan and IA Iwok. 2017. A minimum spanning tree approach of solving a transportation problem. International Journal of Mathematics and Statistics Invention, Vol. 5, 3 (2017), 09--18.","journal-title":"International Journal of Mathematics and Statistics Invention"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/WINCOM.2016.7777228"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.10.005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-5193(87)80063-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-021-00398-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808754"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555806"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_1_12_1","volume-title":"SRC Technical Note","volume":"4","author":"Henzinger Monika Rauch","year":"1997","unstructured":"Monika Rauch Henzinger and Valerie King. 1997 a. Fully dynamic 2-edge connectivity algorithm in polylogarithmic time per operation. SRC Technical Note, Vol. 4 (1997)."},{"key":"e_1_2_1_13_1","volume-title":"24th International Colloquium, ICALP'97 Bologna, Italy, July 7--11","author":"Henzinger Monika R","year":"1997","unstructured":"Monika R Henzinger and Valerie King. 1997 b. Maintaining minimum spanning trees in dynamic graphs. In Automata, Languages and Programming: 24th International Colloquium, ICALP'97 Bologna, Italy, July 7--11, 1997 Proceedings 24. Springer, 594--604."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276715"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977585.ch28"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings. Springer, 742--753","author":"Holm Jacob","year":"2015","unstructured":"Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. 2015. Faster fully-dynamic minimum spanning forest. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14--16, 2015, Proceedings. Springer, 742--753."},{"key":"e_1_2_1_20_1","volume-title":"TheoretiCS","volume":"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 O(\u0142og n (\u0142oglog n)^2) Amortized Expected Time. TheoretiCS, Vol. 2 (2023)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.4.575"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_1_23_1","unstructured":"Jon Kleinberg and Eva Tardos. 2006. Algorithm design. Pearson Education India."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210403"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.3390\/math12071021"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/NAPS.2014.6965353"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402713"},{"key":"e_1_2_1_30_1","first-page":"21","article-title":"Minimum spanning tree application in the currency market","volume":"21","author":"Re\u0161ovsk\u1ef3 Marcel","year":"2013","unstructured":"Marcel Re\u0161ovsk\u1ef3, Denis Horv\u00e1th, Vladim\u00edr Gazda, and Marianna Sini\u010d\u00e1kov\u00e1. 2013. Minimum spanning tree application in the currency market. Biatec, Vol. 21, 7 (2013), 21--23.","journal-title":"Biatec"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_30"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802464"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654960"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715896"},{"key":"e_1_2_1_35_1","first-page":"4","article-title":"Dynamic trees in practice","volume":"14","author":"Tarjan Robert E","year":"2010","unstructured":"Robert E Tarjan and Renato F Werneck. 2010. Dynamic trees in practice. Journal of Experimental Algorithmics (JEA), Vol. 14 (2010), 4--5.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0045-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44985-X_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538584"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00195"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698805"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364329"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:18:47Z","timestamp":1774981127000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709704"],"URL":"https:\/\/doi.org\/10.1145\/3709704","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}