Additive Spanners in Nearly Quadratic Time
Additive Spanners in Nearly Quadratic Time
复制标题
近二次方时间内的加法扳手
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
David P. Woodruff
我们考虑有效找到无向无权图 G（即子图 H）的加法 C 跨度的问题，使得对于所有顶点对 u,v，δ H (u,v) ≤ δ G (u,v) + C，其中 δ 表示最短路径距离。已知对于每个图G，我们可以在O(mn 2/3) 时间内找到一个具有O(n 4/3) 条边的加法6 扳手。未知是否存在常数 C 和具有 o(n 4/3) 条边的附加 C 扳手。此外，对于 C ≤ 5，所有已知的结构都需要 Ω(n 3/2) 边。
We consider the problem of efficiently finding an additive C-spanner of an undirected unweighted graph G, that is, a subgraph H so that for all pairs of vertices u,v, δ H (u,v) ≤ δ G (u,v) + C, where δ denotes shortest path distance. It is known that for every graph G, one can find an additive 6-spanner with O(n 4/3) edges in O(mn 2/3) time. It is unknown if there exists a constant C and an additive C-spanner with o(n 4/3) edges. Moreover, for C ≤ 5 all known constructions require Ω(n 3/2) edges.