Publication: Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
Issued Date
2020-07-06
Resource Type
Other identifier(s)
2-s2.0-85088661218
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Annual ACM Symposium on Parallelism in Algorithms and Architectures. (2020), 51-61
Suggested Citation
Daniel Anderson, Guy E. Blelloch, Kanat Tangwongsan Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model. Annual ACM Symposium on Parallelism in Algorithms and Architectures. (2020), 51-61. doi:10.1145/3350755.3400241 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/57821
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
Author(s)
Other Contributor(s)
Abstract
© 2020 Owner/Author. Algorithms for dynamically maintaining minimum spanning trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optimal algorithms for dense graphs, all existing parallel batch-dynamic algorithms perform polynomial work per update in the worst case for sparse graphs. In this paper, we present the first work-efficient parallel batch-dynamic algorithm for incremental MST, which can insert l edges in O(l log(1+n/l) work in expectation and O(polylog(n)) span w.h.p. The key ingredient of our algorithm is an algorithm for constructing a compressed path tree of an edge-weighted tree, which is a smaller tree that contains all pairwise heaviest edges between a given set of marked vertices. Using our batch-incremental MST algorithm, we demonstrate a range of applications that become efficiently solvable in parallel in the sliding-window model, such as graph connectivity, approximate MSTs, testing bipartiteness, k-certificates, cycle-freeness, and maintaining sparsifiers.