Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
复制标题
DOI：
10.1145/3350755.3400241
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Daniel Anderson;G. Blelloch;Kanat Tangwongsan
中科院分区：
文献类型：
--
作者：
Daniel Anderson;G. Blelloch;Kanat Tangwongsan
动态维护最小生成树(MST)的算法在并行和顺序环境中都受到了极大的关注。虽然前人的工作已经给出了稠密图的最优算法，但现有的所有并行批处理动态算法在稀疏图的最坏情况下每次更新都要执行多项式工作。本文提出了第一个工作效率高的并行批动态增量MST算法，该算法可以在O(L log(1+n/L))期望工作量和O(PolyLog(N))跨度W.H.P.中插入L边。我们算法的关键部分是构造边加权树的压缩路径树的算法，边加权树是一棵较小的树，它包含给定的一组标记顶点之间的所有两两最重的边。使用我们的批增量MST算法，我们展示了一系列在滑动窗口模型中变得高效可并行求解的应用，例如图连通性、近似MST、测试二部性、k证书、无圈和维护稀疏器。
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.