{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:23:57Z","timestamp":1777965837666,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1408940"],"award-info":[{"award-number":["CCF-1408940"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400241","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"51-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Anderson","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kanat","family":"Tangwongsan","sequence":"additional","affiliation":[{"name":"Mahidol University International College, Bangkok, Thailand"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Acar Umut A","year":"2019","unstructured":"Umut A Acar , Daniel Anderson , Guy E Blelloch , and Laxman Dhulipala . 2019 . Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Umut A Acar, Daniel Anderson, Guy E Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_2_1","volume-title":"Parallel Batch-dynamic Trees via Change Propagation. arXiv preprint arXiv:2002.05129 [cs.DS]","author":"Acar Umut A","year":"2020","unstructured":"Umut A Acar , Daniel Anderson , Guy E Blelloch , Laxman Dhulipala , and Sam Westrick . 2020. Parallel Batch-dynamic Trees via Change Propagation. arXiv preprint arXiv:2002.05129 [cs.DS] ( 2020 ). Umut A Acar, Daniel Anderson, Guy E Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-dynamic Trees via Change Propagation. arXiv preprint arXiv:2002.05129 [cs.DS] (2020)."},{"key":"e_1_3_2_1_3_1","unstructured":"Umut A Acar Guy E Blelloch and Jorge L Vittes. 2005. An experimental analysis of change propagation in dynamic trees. In Algorithm Engineering and Experiments (ALENEX).  Umut A Acar Guy E Blelloch and Jorge L Vittes. 2005. An experimental analysis of change propagation in dynamic trees. In Algorithm Engineering and Experiments (ALENEX)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_2_1_6_1","volume-title":"ACM Symposium on Theory of Computing (STOC).","author":"Andr\u00e1s","unstructured":"Andr\u00e1s A. Bencz\u00far and David R. Karger. 1996. Approximating s-t Minimum Cuts in \u00d5(n2) Time . In ACM Symposium on Theory of Computing (STOC). Andr\u00e1s A. Bencz\u00far and David R. Karger. 1996. Approximating s-t Minimum Cuts in \u00d5(n2) Time. In ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_8_1","volume-title":"Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures(SPAA).","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch , Daniel Ferizovic , and Yihan Sun . 2016 . Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures(SPAA). Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures(SPAA)."},{"key":"e_1_3_2_1_9_1","volume-title":"Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Guy","unstructured":"Guy E. Blelloch and Margaret Reid-Miller. 1998 . Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Guy E. Blelloch and Margaret Reid-Miller. 1998. Fast Set Operations Using Treaps. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_10_1","volume-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Prirodved. Spol. v Brne (Acta Societ. Scienc. Natur. Moravicae)3, 3","author":"Boruvka Otakar","year":"1926","unstructured":"Otakar Boruvka . 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Prirodved. Spol. v Brne (Acta Societ. Scienc. Natur. Moravicae)3, 3 ( 1926 ), 37--58. Otakar Boruvka. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Prirodved. Spol. v Brne (Acta Societ. Scienc. Natur. Moravicae)3, 3 (1926), 37--58."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_1_12_1","volume-title":"Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Cole Richard","unstructured":"Richard Cole , Philip N. Klein , and Robert E. Tarjan . 1996 . Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Richard Cole, Philip N. Klein, and Robert E. Tarjan. 1996. Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_29"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0049420"},{"key":"e_1_3_2_1_15_1","unstructured":"Sajal K Das and Paolo Ferragina. 1995. Parallel Dynamic Algorithms for Minimum Spanning Trees. Citeseer. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.24.136&rep=rep1&type=pdf.  Sajal K Das and Paolo Ferragina. 1995. Parallel Dynamic Algorithms for Minimum Spanning Trees. Citeseer. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.24.136&rep=rep1&type=pdf."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012962649900013X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_3_2_1_18_1","volume-title":"1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1","author":"Dijkstra Edsger W","year":"1959","unstructured":"Edsger W Dijkstra 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 ( 1959 ), 269--271. Edsger W Dijkstra et al.1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269--271."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1995.395919"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1157"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58184-7_143"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626496000212"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091666"},{"key":"e_1_3_2_1_26_1","first-page":"1046","article-title":"An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.SIAM J","volume":"20","author":"Gazit Hillel","year":"1991","unstructured":"Hillel Gazit . 1991 . An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.SIAM J . Comput. 20 , 6 (1991), 1046 -- 1067 . Hillel Gazit. 1991. An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.SIAM J. Comput. 20, 6 (1991), 1046--1067.","journal-title":"Comput."},{"key":"e_1_3_2_1_27_1","volume-title":"Parallel Minimum Cuts in Near-linear Work and Low Depth. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Geissmann Barbara","year":"2018","unstructured":"Barbara Geissmann and Lukas Gianinazzi . 2018 . Parallel Minimum Cuts in Near-linear Work and Low Depth. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Barbara Geissmann and Lukas Gianinazzi. 2018. Parallel Minimum Cuts in Near-linear Work and Low Depth. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_1_29_1","unstructured":"Ashish Goel Michael Kapralov and Ian Post. 2012. Single pass sparsification in the streaming model with edge deletions.arXiv preprint arXiv:1203.4900 [cs.DS](2012).  Ashish Goel Michael Kapralov and Ian Post. 2012. Single pass sparsification in the streaming model with edge deletions.arXiv preprint arXiv:1203.4900 [cs.DS](2012)."},{"key":"e_1_3_2_1_30_1","volume-title":"Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time. ACM Trans. Algorithms14,2","author":"Goranci Gramoz","year":"2018","unstructured":"Gramoz Goranci , Monika Henzinger , and Mikkel Thorup . 2018. Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time. ACM Trans. Algorithms14,2 ( 2018 ), 17:1--17:21. Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. 2018. Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time. ACM Trans. Algorithms14,2 (2018), 17:1--17:21."},{"key":"e_1_3_2_1_31_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures(SPAA).","author":"Gu Yan","unstructured":"Yan Gu , Julian Shun , Yihan Sun , and Guy E. Blelloch . 2015. A Top-Down Parallel Semisort . In ACM Symposium on Parallelism in Algorithms and Architectures(SPAA). Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A Top-Down Parallel Semisort. In ACM Symposium on Parallelism in Algorithms and Architectures(SPAA)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_33_1","volume-title":"Faster Fully-Dynamic Minimum Spanning Forest. In European Symposium on Algorithms(ESA).","author":"Holm Jacob","year":"2015","unstructured":"Jacob Holm , Eva Rotenberg , and Christian Wulff-Nilsen . 2015 . Faster Fully-Dynamic Minimum Spanning Forest. In European Symposium on Algorithms(ESA). Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. 2015. Faster Fully-Dynamic Minimum Spanning Forest. In European Symposium on Algorithms(ESA)."},{"key":"e_1_3_2_1_34_1","volume-title":"An introduction to parallel algorithms","author":"J\u00e1J\u00e1 Joseph","unstructured":"Joseph J\u00e1J\u00e1 . 1992. An introduction to parallel algorithms . Vol. 17 . Addison-Wesley Reading . Joseph J\u00e1J\u00e1. 1992. An introduction to parallel algorithms. Vol. 17. Addison-Wesley Reading."},{"key":"e_1_3_2_1_35_1","volume-title":"Pr\u00e1ca Moravsk\u00e9 Pr\u00edrodovedeck\u00e9 Spolecnosti 6","author":"Jarn\u00edk Vojtech","year":"1930","unstructured":"Vojtech Jarn\u00edk . 1930. O jist\u00e9m probl\u00e9mu minim \u00e1ln\u00edm . Pr\u00e1ca Moravsk\u00e9 Pr\u00edrodovedeck\u00e9 Spolecnosti 6 ( 1930 ), 57--63. Vojtech Jarn\u00edk. 1930.O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ca Moravsk\u00e9 Pr\u00edrodovedeck\u00e9 Spolecnosti 6 (1930), 57--63."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.223028"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90084-1"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_39_1","volume-title":"Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest. In ACM Symposiumon Parallelism in Algorithms and Architectures (SPAA).","author":"Kopelowitz Tsvi","year":"2018","unstructured":"Tsvi Kopelowitz , Ely Porat , and Yair Rosenmutter . 2018 . Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest. In ACM Symposiumon Parallelism in Algorithms and Architectures (SPAA). Tsvi Kopelowitz, Ely Porat, and Yair Rosenmutter. 2018. Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest. In ACM Symposiumon Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_2_1_41_1","first-page":"47","article-title":"Parallel Tree Contraction Part 1: Fundamentals","volume":"5","author":"Miller Gary L.","year":"1989","unstructured":"Gary L. Miller and John H. Reif . 1989 . Parallel Tree Contraction Part 1: Fundamentals . In Randomness and Computation , Vol. 5. 47 -- 72 . Gary L. Miller and John H. Reif. 1989. Parallel Tree Contraction Part 1: Fundamentals. In Randomness and Computation, Vol. 5. 47--72.","journal-title":"Randomness and Computation"},{"key":"e_1_3_2_1_42_1","volume-title":"International Conference on Parallel Processing (ICPP).","author":"Pawagi Shaunak","year":"1989","unstructured":"Shaunak Pawagi . 1989 . A parallel algorithm for multiple updates of minimum spanning trees . In International Conference on Parallel Processing (ICPP). Shaunak Pawagi. 1989. A parallel algorithm for multiple updates of minimum spanning trees. In International Conference on Parallel Processing (ICPP)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228509"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90098-0"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_3_2_1_46_1","volume-title":"International Parallel Processing Symposium(IPPS).","author":"Shen Xiaojun","year":"1993","unstructured":"Xiaojun Shen and Weifa Liang . 1993 . A parallel algorithm for multiple edge up-dates of minimum spanning trees . In International Parallel Processing Symposium(IPPS). Xiaojun Shen and Weifa Liang. 1993. A parallel algorithm for multiple edge up-dates of minimum spanning trees. In International Parallel Processing Symposium(IPPS)."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_41"},{"key":"e_1_3_2_1_48_1","volume-title":"A data structure for dynamic trees. J. of computer and system sciences 26, 3","author":"Sleator Daniel D","year":"1983","unstructured":"Daniel D Sleator and Robert Endre Tarjan . 1983. A data structure for dynamic trees. J. of computer and system sciences 26, 3 ( 1983 ), 362--391. Daniel D Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. of computer and system sciences 26, 3 (1983), 362--391."},{"key":"e_1_3_2_1_49_1","volume-title":"On finding and updating spanning trees and shortest paths.SIAM J. on Computing4, 3","author":"Spira Philip M.","year":"1975","unstructured":"Philip M. Spira and A Pan . 1975. On finding and updating spanning trees and shortest paths.SIAM J. on Computing4, 3 ( 1975 ), 375--380. Philip M. Spira and A Pan. 1975. On finding and updating spanning trees and shortest paths.SIAM J. on Computing4, 3 (1975), 375--380."},{"key":"e_1_3_2_1_50_1","unstructured":"Xiaoming Sun and David P Woodruff. 2015. Tight bounds for graph problems in insertion streams. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM).  Xiaoming Sun and David P Woodruff. 2015. Tight bounds for graph problems in insertion streams. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)."},{"key":"e_1_3_2_1_51_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_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90020-8"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/646240.756752"},{"key":"e_1_3_2_1_54_1","volume-title":"An efficient parallel algorithm for updating minimum spanning trees. Theoretical Computer Science (TCS)58, 1--3","author":"Varman Peter","year":"1988","unstructured":"Peter Varman and Kshitij Doshi . 1988. An efficient parallel algorithm for updating minimum spanning trees. Theoretical Computer Science (TCS)58, 1--3 ( 1988 ), 379--397. Peter Varman and Kshitij Doshi. 1988. An efficient parallel algorithm for updating minimum spanning trees. Theoretical Computer Science (TCS)58, 1--3 (1988), 379--397."}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400241","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400241","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:35Z","timestamp":1750202015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":54,"alternative-id":["10.1145\/3350755.3400241","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400241","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}