Near-Optimal Light Spanners
Near-Optimal Light Spanners
复制标题
近乎最佳的轻型扳手
DOI：
10.1145/3199607
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
S. Chechik;Christian Wulff
加权无向图\(G\)的一个生成树\(H\)是一个“稀疏”子图，它近似保留了\(G\)中每对顶点之间的距离。对于某个参数\(\delta\geq1\)，如果\(H\)中每对顶点之间的距离至多比\(G\)中的距离大\(\delta\)倍，我们就称\(H\)是\(G\)的一个\(\delta\)-生成树。在这种情况下，我们说\(H\)的伸展度为\(\delta\)。生成树稀疏性的两个主要度量是大小（边的数量）和总权重（生成树中边的权重之和）。众所周知，对于任何正整数\(k\)，人们可以有效地构造一个具有\(O(n^{1 + 1/k})\)条边的\((2k - 1)\)-生成树，其中\(n\)是顶点的数量\([2]\)。这种大小 - 伸展度的权衡被推测基于埃尔德什的围长猜想是最优的\([17]\)。然而，对于第二个度量，当前的技术水平还不是最优的。最近，埃尔金、尼曼和所罗门\([ICALP 14]\)对贪心算法提出了一种改进的分析，证明贪心算法具有\((2k - 1)\cdot(1 + \varepsilon)\)的伸展度和\(O_{\varepsilon}((k / \log k)\cdot\omega(MST(G))\cdot n^{1/k})\)的总边权重，其中\(\omega(MST(G))\)是\(G\)的最小生成树的权重。钱德拉等人\([SOCG 92]\)之前的分析得到\((2k - 1)\cdot(1 + \varepsilon)\)的伸展度和\(O_{\varepsilon}(k\omega(MST(G))n^{1/k})\)的总边权重。因此，埃尔金等人将生成树的权重提高了\(\log k\)倍。在本文中，我们完全从权重中去除了\(k\)因子，提出了一个具有\((2k - 1)\cdot(1 + \varepsilon)\)伸展度、\(O_{\varepsilon}(\omega(MST(G))n^{1/k})\)总权重和\(O(n^{1 + 1/k})\)条边的生成树。在伸展度的\((1 + \varepsilon)\)因子范围内，这与埃尔德什的围长猜想\([17]\)相匹配。
A spanner H of a weighted undirected graph G is a “sparse” subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a δ-spanner of G for some parameter δ ≥ 1 if the distance in H between every vertex pair is at most a factor δ bigger than in G. In this case, we say that H has stretch δ. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k, one can efficiently construct a (2k − 1)-spanner of G with O(n1+1/k) edges where n is the number of vertices [2]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdős [17]. However, the current state of the art for the second measure is not yet optimal. Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2k − 1) · (1 + ε) stretch and total edge weight of Oε ((k/ log k) · ω (MST(G)) · n1/k), where ω(MST(G)) is the weight of a MST of G. The previous analysis by Chandra et al. [SOCG 92] admitted (2k − 1) · (1 + ε) stretch and total edge weight of Oε(kω(MST(G))n1/k). Hence, Elkin et al. improved the weight of the spanner by a log k factor. In this article, we completely remove the k factor from the weight, presenting a spanner with (2k − 1) · (1 + ε) stretch, Oε(ω(MST(G))n1/k) total weight, and O(n1+1/k) edges. Up to a (1 + ε) factor in the stretch this matches the girth conjecture of Erdős [17].