A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
复制标题
一般图的线性大小对数拉伸路径报告距离预言机
DOI：
10.1145/2888397
复制
发表时间：
2016
影响因子：
1.3
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Elkin, Michael;Pettie, Seth
Thorup和Zwick [2001 a]提出了一个具有以下性质的地标距离预言。给定n-顶点无向图G =（V，E）和一个参数k = 1，2，.，它们的预言机的大小为O（kn 1 + 1/k），并且在查询（u，v）时，它在u和v之间构造一条长度为δ（u，v）的路径，使得dG（u，v）<$δ（u，v）<$（2k− 1）dG（u，v）。Thorup和Zwick [2001 a]的oracle的查询时间是O（k）（除了返回路径的长度），随后它被改进为O（1）[Wulff-Nilsen 2012; Zahik 2014]。Thorup和Zwick [2001 a]预言的一个主要缺点是它的空间是Ω（n· logn）。Mendel和Naor [2006]设计了一个具有spaceO（n1 + 1/k）和stretchO（k）的预言机，但他们的预言机只能报告距离估计而不能报告实际路径。在这篇文章中，我们设计了一个路径报告距离预言机，其大小为O（n1 + 1/k），stretchO（k），查询时间为O（nε），对于任意小的常数ε > 0。特别是，fork= logn，我们的oracle使用线性大小提供对数拉伸。我们的预言机的另一个变体具有sizeO（nloglogn），多对数拉伸和查询时间O（loglogn）。对于未加权图，我们设计了一个距离预言机，对于函数β（·），具有乘法拉伸O（1），加法拉伸O（β（k）），空间O（n1 + 1/k），查询时间O（nε），对于任意小的常数ε > 0。在这些预言中，乘法拉伸和大小之间的权衡远远低于Erdans的围长猜想阈值（拉伸为2k− 1，大小为O（n1 + 1/k））。打破围长猜想的折衷是通过展示加法拉伸β（k）和大小O（n1 + 1/k）之间不同性质的折衷来实现的。Elkin和Peleg [2001]的（1 + ε，β）-空间结构也展示了类似的权衡。然而，到目前为止，（1 + ε，β）-空间在距离预言机的世界里还没有对应的空间，我们在得到这些结果的过程中开发的一个重要的新工具是距离保持路径报告预言机。我们相信这个神谕是独立的利益。
Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given ann-vertex undirected graphG= (V,E) and a parameterk= 1, 2, …, their oracle has sizeO(kn1 + 1/k), and upon a query (u,v) it constructs a path Π betweenuandvof length δ(u,v) such thatdG(u,v) ⩽ δ(u,v) ⩽ (2k− 1)dG(u,v). The query time of the oracle from Thorup and Zwick [2001a] isO(k) (in addition to the length of the returned path), and it was subsequently improved toO(1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is Ω(n· logn). Mendel and Naor [2006] devised an oracle with spaceO(n1 + 1/k) and stretchO(k), but their oracle can only report distance estimates and not actual paths. In this article, we devise a path-reporting distance oracle with sizeO(n1 + 1/k), stretchO(k), and query timeO(nε), for an arbitrarily small constant ε > 0. In particular, fork= logn, our oracle provides logarithmic stretch using linear size. Another variant of our oracle has sizeO(nloglogn), polylogarithmic stretch, and query timeO(loglogn).For unweighted graphs, we devise a distance oracle with multiplicative stretchO(1), additive stretchO(β(k)), for a function β(·), spaceO(n1 + 1/k), and query timeO(nε), for an arbitrarily small constant ε > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdős’s girth conjecture threshold (which is stretch 2k− 1 and sizeO(n1 + 1/k)). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch β(k) and sizeO(n1 + 1/k). A similar type of tradeoff was exhibited by a construction of (1 + ε, β)-spanners due to Elkin and Peleg [2001]. However, so far (1 + ε, β)-spanners had no counterpart in the distance oracles’ world.An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.
登录
查看更多内容
DOI：
10.1137/090776573
发表时间：
2004
期刊：
45th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Roditty;Uri Zwick
通讯作者：
Uri Zwick
未加权图的距离预言：打破具有恒定加性误差的二次障碍
DOI：
10.1007/978-3-540-70575-8_50
发表时间：
2008
期刊：
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
影响因子：
--
作者：
Surender Baswana;Akshay Gaur;Sandeep Sen;Jayant Upadhyay
通讯作者：
Jayant Upadhyay
DOI：
10.1145/62212.62217
发表时间：
1988
期刊：
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
影响因子：
--
作者：
D. Peleg;E. Upfal
通讯作者：
E. Upfal
Ramsey 分区和邻近数据结构
DOI：
--
发表时间：
2005
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Mendel;A. Naor
通讯作者：
A. Naor
稀疏图中更快的近似距离查询和紧凑路由
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
R. Agarwal;Brighten Godfrey;Sariel Har
通讯作者：
Sariel Har