论文标题
边缘连接的顶点稀疏
Vertex Sparsification for Edge Connectivity
论文作者
论文摘要
图形压缩或稀疏是一个基本的信息理论和计算问题。该研究领域的一个主要开放问题是$（1+ε）$ - 近似剪切的顶点散布器，大小接近端子数量。为了朝着这个目标迈出的一步，我们研究了问题的阈值版本：对于给定参数$ c $，找到一个较小的图，我们称之为连接性-c $ c $模仿网络，该网络可保留$ k $终端之间的连接，完全达到$ c $的值。我们表明，连接性 - $ c $模仿$ o（kc^4）$ edges的网络，并且可以在时间$ m（c \ log n）^{o（c）} $中找到。我们还提供了一种单独的算法，该算法用$ k \ cdot o（c）^{2c} $ edge构建此类图，$ mc^{o（c）} \ log log^{o（1）} n $。这些结果导致了第一个数据结构，用于回答有关$ c \ ge 4 $ in查询的$ c \ ge 4 $ toce-ge-ge-geconnectivity查询的第一个数据结构。
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+ε)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(c\log n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k \cdot O(c)^{2c}$ edges in time $mc^{O(c)}\log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
