论文标题
确定性分布式稀疏和超巨大跨度和连接证书
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
论文作者
论文摘要
本文介绍了有效的分布式算法，这些算法对于图形稀疏领域的许多基本问题： 我们提供了第一个确定性分布式算法，该算法在$ \ textrm {polylog}（n）$ rounds中计算超固定扳手的加权图。具体而言，我们的算法输出了一个跨度子图，只有$ n+o（n）$ edges，其中成对距离的最多为$ o（\ log n \; \ cdot \; 2^{o（\ log log^* n）}）$。 我们提供了$ \ textrm {polylog}（n）$ - 圆形确定性分布式算法，该算法计算具有拉伸$（2K-1）$和$ O（NK + N^{1 + 1 + 1/k} \ log k）$ edges nif wepracy Graphs，并使用$ O（NK + 1 + 1/k} \ log K）$ edge的扳手（nk + n^{1 + n^{1 + 1/k} \ log k）$ edge，并使用$ O（N^{1 + 1 + 1 + 1/k} k）$ edges complate frofforgs comptive。 我们介绍了第一个$ \ textrm {polylog}（n）$ - 圆形随机分布式算法，该算法计算稀疏连接证书。对于$ n $ node Graph $ g $，连接性$ k $的证书是跨度子图$ h $，当时是$ k $ - edge-edgeented，并且仅当$ g $为$ k $ - edge-edge-ennected时，此子级$ h $在具有$ o（nk）$ edges时被称为稀疏。我们的算法达到了$（1 + o（1））NK $边缘的稀疏性，该边缘在$ 2（1 + O（1））$最佳因素之内。
This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in $\textrm{polylog}(n)$ rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only $n+o(n)$ edges in which the pairwise distances are stretched by a factor of at most $O(\log n \;\cdot\; 2^{O(\log^* n)})$. We provide a $\textrm{polylog}(n)$-round deterministic distributed algorithm that computes a spanner with stretch $(2k-1)$ and $O(nk + n^{1 + 1/k} \log k)$ edges in unweighted graphs and with $O(n^{1 + 1/k} k)$ edges in weighted graphs. We present the first $\textrm{polylog}(n)$-round randomized distributed algorithm that computes a sparse connectivity certificate. For an $n$-node graph $G$, a certificate for connectivity $k$ is a spanning subgraph $H$ that is $k$-edge-connected if and only if $G$ is $k$-edge-connected, and this subgraph $H$ is called sparse if it has $O(nk)$ edges. Our algorithm achieves a sparsity of $(1 + o(1))nk$ edges, which is within a $2(1 + o(1))$ factor of the best possible.
