Weighted Additive Spanners
Weighted Additive Spanners
复制标题
加权附加扳手
DOI：
10.1007/978-3-030-60440-0_32
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Spence, R
中科院分区：
文献类型：
--
作者：
Ahmed, R;Bodwin, G;Darabi, F;Kobourov, S;Spence, R
图的 SpannerG 是一个子图 H，它近似保留 G 中的最短路径距离。 Spanner 通常用于压缩对应于加权输入图的度量空间上的计算。只要误差是乘法测量的，经典的扳手结构就可以无缝地处理边缘重量。在这项工作中，我们研究是否可以类似地将具有纯加性误差的扳手结构扩展到加权图。这些扩展并不是立竿见影的，因为关于最短路径邻域大小的关键引理对于加权图来说是失败的。尽管如此，我们还是恢复了一个合适的摊销版本，这让我们能够证明经典和未加权扳手（全对和成对）到加权扳手的直接扩展，其中W是最大边缘权重。具体来说，我们表明加权图 G 分别包含大小为 和 的所有对（成对）和加权扳手。由于技术原因，非加重扳手变成了加重扳手；缩小这个误差差距是一个有趣的悬而未决的问题。也就是说，我们证明 G 包含大小为 () 的所有对（成对）加权扳手。
Aspannerof a graphGis a subgraphHthat approximately preserves shortest path distances inG. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measuredmultiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purelyadditiveerror to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classicandunweighted spanners (both all-pairs and pairwise) toandweighted spanners, whereWis the maximum edge weight. Specifically, we show that a weighted graphGcontains all-pairs (pairwise)andweighted spanners of sizeand(and) respectively. For a technical reason, theunweighted spanner becomes aweighted spanner; closing this error gap is an interesting remaining open problem. That is, we show thatGcontains all-pairs (pairwise)weighted spanners of size().
登录
查看更多内容
新型增材扳手
DOI：
--
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
近二次方时间内的加法扳手
DOI：
--
发表时间：
2010
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
David P. Woodruff
通讯作者：
David P. Woodruff
DOI：
10.1145/380752.380797
发表时间：
2001-07
期刊：
--
影响因子：
--
作者：
Michael Elkin;D. Peleg
通讯作者：
Michael Elkin;D. Peleg
4/3 加法扳手指数很紧
DOI：
10.1145/3088511
发表时间：
2015
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Amir Abboud;Gregory Bodwin
通讯作者：
Gregory Bodwin