A $t$-spanner of a graph is a subgraph that $t$-approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a sparse spanner: it computes a $t$-spanner with $n^{1+O(1/t)}$ edges by repeatedly choosing any edge which does not close a cycle of chosen edges with $t+1$ or fewer edges. We demonstrate that the greedy algorithm computes a $t$-spanner with $t^3\cdot \log^3 n \cdot n^{1 + O(1/t)}$ edges even when a matching of such edges are added in parallel. In particular, it suffices to repeatedly add any matching where each individual edge does not close a cycle with $t +1$ or fewer edges but where adding the entire matching might. Our analysis makes use of and illustrates the power of new advances in length-constrained expander decompositions.
翻译：一张图的 $t$-跨度图是一个子图，它以$t$-近似的方式表示任意两点之间的距离。贪心算法是一种构建稀疏跨度图最简单和最广泛研究的方法之一：它通过重复选择不会使选择的边形成带有 $t+1$ 条边或更少边的循环的边来计算 $t$-跨度图，其边数为 $n^{1+O(1/t)}$。我们证明了贪心算法即使在并行加入具有此类边的任何匹配时也可以计算出 $t$-跨度图，其边数为 $t^3\cdot \log^3 n \cdot n^{1 + O(1/t)}$。特别地，只需要重复添加任何匹配，其中每个单独的边都不会形成 $t+1$ 条边或更少边的循环，但加入整个匹配可能会。我们的分析利用并展开分解的新进展，从而阐明了其威力。
相关内容
微信扫码咨询专知VIP会员