Improved weighted additive spanners
Improved weighted additive spanners
复制标题
改进的加重添加剂扳手
DOI：
10.1007/s00446-022-00433-x
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Ofer Neiman
中科院分区：
文献类型：
--
作者：
Michael Elkin;Yuval Gitlitz;Ofer Neiman
图扳手和模拟器是稀疏结构，近似保留原始图的距离。虽然在增性扳手方面已经进行了大量的工作，但到目前为止，人们对加权图的关注还很少。直到最近，艾哈迈德等人才报道。 （参见：Adler I、Müller H（编）计算机科学中的图论概念 - 第 46 届国际研讨会，WG 2020，英国利兹）。将大小为 $$O(n^{3/2})$$ O ( n 3 / 2 ) （分别为 $$O(n^{7/5})$$ O ( n 7 / 5 ) ）的未加权图的经典 +2（分别为 +4）扳手扩展到加权设置，其中附加误差为 $$+2W$$ + 2 W（分别为 $$+4W$$ + 4 W） ）。这意味着对于每一对 u , v ，加性拉伸至多为 $$+2W_{u,v}$$ + 2 W u , v ，其中 $$W_{u,v}$$ W u , v 是最短 $$u-v$$ u - v 路径上的最大边权重（权重已标准化，因此最小边权重为 1）。此外，据艾哈迈德等人报道。 （参见：Adler I、Müller H（编）计算机科学中的图论概念 - 第 46 届国际研讨会，WG 2020，英国利兹）。显示了一种随机算法，产生 $$+8W_{max}$$ + 8 W max 扳手，大小为 $$O(n^{4/3})$$ O ( n 4 / 3 ) ，这里 $$W_{max}$$ W max 是整个图中的最大边权重。在这项工作中，我们通过为 $$+(6+\varepsilon )W$$ + ( 6 + ε ) W 扳手设计一个简单的确定性算法来改进后一个结果，该算法适用于大小为 $$O(n^{4/3})$$ O ( n 4 / 3 ) 的加权图（对于任何常数 $$\varepsilon >0$$ ε > 0 ），从而几乎匹配大小的经典 +6 扳手$$O(n^{4/3})$$ O ( n 4 / 3 ) 对于未加权图。此外，我们展示了 $$+(2+\varepsilon )W$$ + ( 2 + ε ) W 子集扳手，其大小为 $$O(n\cdot \sqrt{\vert S\vert })$$ O ( n · | S | ) ，改进了 Ahmed 等人报告的 $$+4W_{max}$$ + 4 W max 结果。 （参见：Adler I、Müller H（编）计算机科学中的图论概念 - 第 46 届国际研讨会，WG 2020，英国利兹）。 （具有相同的尺寸）。我们还展示了一个简单的随机算法，适用于大小为 $${\tilde{O}}(n^{4/3})$$ O ~ ( n 4 / 3 ) 的 $$+4W$$ + 4 W 模拟器。此外，我们还表明我们的技术适用于具有线性尺寸的非常稀疏的附加扳手。 Abboud A、Bodwin G (J ACM 64(4):28–12820 2017) 证明，此类扳手必须承受多项式大拉伸。对于加权图，我们使用简单确定性算法的变体，产生线性大小 $$+{\tilde{O}}(\sqrt{n}\cdot W)$$ + O ~ ( n · W ) 扳手，并且我们还获得了大小和拉伸之间的权衡。最后，概括了 Dor D 等人的技术。 (SIAM J Comput 29:1740–1759, 2000) 对于未加权图，我们设计了一种有效的随机算法，为大小为 $${\tilde{O}}(n^{3/2})$$ O ~ ( n 3 / 2 ) in $${\tilde{O}}(n^2)$$ O ~ ( n 的加权图生成 $$+2W$$ + 2 W 扳手2）时间。
Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $$O(n^{3/2})$$ O ( n 3 / 2 ) (resp., $$O(n^{7/5})$$ O ( n 7 / 5 ) ) to the weighted setting, where the additive error is $$+2W$$ + 2 W (resp., $$+4W$$ + 4 W ). This means that for every pair u , v , the additive stretch is at most $$+2W_{u,v}$$ + 2 W u , v , where $$W_{u,v}$$ W u , v is the maximal edge weight on the shortest $$u-v$$ u - v path (weights are normalized so that the minimum edge weight is 1). In addition, as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). showed a randomized algorithm yielding a $$+8W_{max}$$ + 8 W max spanner of size $$O(n^{4/3})$$ O ( n 4 / 3 ) , here $$W_{max}$$ W max is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $$+(6+\varepsilon )W$$ + ( 6 + ε ) W spanner for weighted graphs with size $$O(n^{4/3})$$ O ( n 4 / 3 ) (for any constant $$\varepsilon >0$$ ε > 0 ), thus nearly matching the classical +6 spanner of size $$O(n^{4/3})$$ O ( n 4 / 3 ) for unweighted graphs. Furthermore, we show a $$+(2+\varepsilon )W$$ + ( 2 + ε ) W subsetwise spanner of size $$O(n\cdot \sqrt{\vert S\vert })$$ O ( n · | S | ) , improving the $$+4W_{max}$$ + 4 W max result of as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). (that had the same size). We also show a simple randomized algorithm for a $$+4W$$ + 4 W emulator of size $${\tilde{O}}(n^{4/3})$$ O ~ ( n 4 / 3 ) . In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. It was proved by Abboud A, Bodwin G (J ACM 64(4):28–12820 2017) that such spanners must suffer polynomially large stretches. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $$+{\tilde{O}}(\sqrt{n}\cdot W)$$ + O ~ ( n · W ) spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of Dor D et al. (SIAM J Comput 29:1740–1759, 2000) for unweighted graphs, we devise an efficient randomized algorithm producing a $$+2W$$ + 2 W spanner for weighted graphs of size $${\tilde{O}}(n^{3/2})$$ O ~ ( n 3 / 2 ) in $${\tilde{O}}(n^2)$$ O ~ ( n 2 ) time.
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth
加权附加扳手
DOI：
10.1007/978-3-030-60440-0_32
发表时间：
2020
期刊：
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG
影响因子：
--
作者：
Ahmed, R;Bodwin, G;Darabi, F;Kobourov, S;Spence, R
通讯作者：
Spence, R