Additive Spanners and Distance Oracles in Quadratic Time
Additive Spanners and Distance Oracles in Quadratic Time
复制标题
二次时间内的加法扳手和距离预言
DOI：
10.4230/lipics.icalp.2017.64
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. B. T. Knudsen
中科院分区：
文献类型：
--
作者：
M. B. T. Knudsen
令$ g $为未加权的未方向图。 $ g $的添加$ k $ -spanner是一个子图$ h $，近似于$+k $的添加误差之间的所有距离，也就是说，它满足$ d_h（u，v）\ le d_g（u，v）+k $用于所有节点$ u，v $，其中$ d $是最短的路径距离。我们给出了一种确定性算法，该算法构建一个添加$ o \！\ left（1 \右）$ - 带有$ o \！\ left（n^{4/3} \ right）$ o \！ （n^2 \右）$时间。应将其与Woodruff的随机Monte Carlo算法[ICALP 2010]与预期的$ o \！\ left（n^{4/3} \ log^3 n \ right）提供添加剂$ 6 $ spanner。时间$ o \！\ left（n^2 \ log^2 n \ right）$。
$（\ alpha，\ beta）$ - $ g $的大约距离Oracle是一个数据结构，该数据结构支持$ g $中的一对节点之间的以下距离查询。给定两个节点$ u $，$ v $它可以在恒定时间内计算距离估计$ \ tilde {d} $满足$ d \ le \ tilde {d} \ le \ le \ le \ alpha d + beta $ with是$ u $和$ v $ in $ g $的距离。 sommer [ialp 2016]给出了一个随机的蒙特卡洛$（2,1）$ - 尺寸$ o \！\ left（n^{5/3} \ text {poly} \ log n \ right）的距离时间$ o \！\ left（n^2 \ text {poly} \ log n \ right）$。作为添加$ o（1）$ - 扳手的应用，我们改善了Sommer [ICALP 2016]的构造，并给出了Las Vegas $（2,1）$ - 尺寸$ o \！\ left的距离（N^ {5/3} \ right）$ in Time $ o \！\ left（n^2 \ right）$。这也意味着一种算法，即在$ o \！\ left（n^2 \右）中给出了$ g $中所有节点的大约距离，以改进$ o \！\！\ left（n^2 \ log n \ n \右）$算法Baswana和Kavitha [Sicomp 2010]。
Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in expected time $O\!\left(n^2\log^2 n\right)$.
An $(\alpha,\beta)$-approximate distance oracle for $G$ is a data structure that supports the following distance queries between pairs of nodes in $G$. Given two nodes $u$, $v$ it can in constant time compute a distance estimate $\tilde{d}$ that satisfies $d \le \tilde{d} \le \alpha d + \beta$ where $d$ is the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an application of the additive $O(1)$-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm by Baswana and Kavitha [SICOMP 2010].
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska