Better Distance Preservers and Additive Spanners
Better Distance Preservers and Additive Spanners
复制标题
更好的距离保持器和附加扳手
DOI：
10.1145/3490147
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Williams, Virginia Vassilevska
中科院分区：
文献类型：
--
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
我们研究了两种常用的绘制输入图的最短路径距离的方法。第一个是距离保持器，它是与给定需求对集合上的原始图的距离一致的稀疏子图。以前关于距离保持的工作只利用了最短路径的一个简单的结构属性，称为一致性，指出人们可以打破最短路径的束缚，使得没有两条路径相交、分开，然后再相交。通过给出一致性幂的一个下界和一个多项式超越它的新的一般上界，我们证明了仅有一致性是不足以理解距离保持的。具体地说，我们的新上界是n节点无向赋权图的一个非需求对在O(n2/3p2/3+np1/3边)上有一个距离保持。我们猜想右界ISO(n2/3p2/3+n)或更好.本文的第二部分利用这些距离保持器构造了一个新的加性扳手，这些加性扳手是保持所有成对距离直到一个加性误差函数的子图.对于边数相对较少的图，我们给出了改进的误差界；例如，我们证明了所有图都有误差为+O(n3/7+ε)的边数为Ono(N)的边。我们的建设可以被视为流行的路径购买框架向更大半径的集群的延伸。
We study two popular ways to sketch the shortest path distances of an input graph. The first isdistance preservers, which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, calledconsistency, stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that anypdemand pairs in ann-node undirected unweighted graph have a distance preserver on O(n2/3p2/3+np1/3edges. We leave a conjecture that the right bound isO(n2/3p2/3+n) or better.The second part of this paper leverages these distance preservers in a new construction ofadditive spanners, which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners onO(n)edges with +O(n3/7 + ε) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
登录
查看更多内容
新型增材扳手
DOI：
--
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
用于构造 T 形扳手和具有拉伸 t 的路径的快速算法
DOI：
--
发表时间：
1993
期刊：
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
影响因子：
--
作者：
E. Cohen
通讯作者：
E. Cohen
一种用于维护稀疏扳手的近乎最优的分布式全动态算法
影响因子：
1.3
作者：
Michael Elkin
通讯作者：
Michael Elkin
二次时间内的加法扳手和距离预言
DOI：
10.4230/lipics.icalp.2017.64
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
M. B. T. Knudsen
通讯作者：
M. B. T. Knudsen
在分布式和流式模型中构建 (1+,ε,β)-spanner 的高效算法
DOI：
10.1145/1011767.1011791
发表时间：
2004
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Michael Elkin;Jian Zhang
通讯作者：
Jian Zhang