论文标题
工作有效的批处理最小跨越树木，并应用于滑动窗口模型
Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
论文作者
论文摘要
用于动态维护最小跨树（MST）的算法在平行和顺序设置中都受到了很多关注。虽然先前的工作给出了密集图的最佳算法，但在最坏情况下，所有现有的平行批次动态算法每次更新进行多项式工作。在本文中，我们介绍了第一个用于增量MST的工作效率平行批次 - 动态算法，它可以将$ \ ell $ edges插入$ o（\ ell \ log \ log \ log（1+n/\ ell））$中的期望值和$ o（\ text {polylog}（n））$ span $ span w.h.p.我们算法的关键成分是一种用于构造边缘加权树的压缩路径树的算法，该树是一棵较小的树，包含一组给定的标记顶点之间的所有成对重边。使用我们的批处理MST算法，我们演示了一系列应用程序，这些应用在滑动窗口模型中可以有效地解决，例如图形连接性，近似MST，测试两部分，$ k $ co $ c $ cobertificates，cyclefificates，cycle-croce oterientes，cycle-wersementys＆cycle-forementys＆cartifiers＆维护和维持Sparsifiers。
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 $\ell$ edges in $O(\ell \log(1+n/\ell))$ work in expectation and $O(\text{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.
