Fast algorithms for constructing t-spanners and paths with stretch t
Fast algorithms for constructing t-spanners and paths with stretch t
复制标题
用于构造 T 形扳手和具有拉伸 t 的路径的快速算法
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
E. Cohen
中科院分区：
文献类型：
--
作者：
E. Cohen
加权图中两个顶点之间的距离就是它们之间最小权重路径的权重。如果一条路径的权重最多是其端点间距离的 t 倍，则该路径的伸展度为 t。我们考虑加权无向图 G=(V,E)，并提出了计算伸展率为 2/spl les/t/spl les/log n 的路径的算法。我们提出了一种 O/spl tilde/((m+k)n/sup (2+/spl epsiv///t))时间随机算法，它能找到 k 对指定顶点之间的路径；我们还提出了一种 O/spl tilde/((m+ns)n/sup 2(1+log(n)/sup m+/spl epsiv/)/t/)确定性算法，它能找到从 s 个指定来源到所有其他顶点的路径（对于任何固定的 /spl epsiv/>0）、其中 n=|V|，m=|E|。图 G 的 tspanner 是 G 顶点上的加权边集合，使得 spanner 中的距离不小于 G 中相应距离的 t 倍。我们在 O/spl tilde/(mn/sup(2+/spl epsiv///t))预期时间内（对于任何固定的/spl epsiv/>0）构造了大小为 O/spl tilde/(n/sup 1+(2+/spl epsiv///t))的 t-疏量，这比以前能实现的更快地构造了更稀疏的疏量（快了 n/sup (3+2/t) 倍）。我们还提供了高效的并行构造。我们的算法基于被称为 "对偶覆盖 "的新结构和一种高效构建它们的新方法。
The distance between two vertices in a weighted graph is the weight of a minimum-weight path between them. A path has stretch t if its weight is at most t times the distance between its end points. We consider a weighted undirected graph G=(V, E) and present algorithms that compute paths with stretch 2/spl les/t/spl les/log n. We present a O/spl tilde/((m+k)n/sup (2+/spl epsiv///t)) time randomized algorithm that finds paths between k specified pairs of vertices and a O/spl tilde/((m+ns)n/sup 2(1+log(n)/ /sup m+/spl epsiv/)/t/) deterministic algorithm that finds paths from s specified sources to all other vertices (for any fixed /spl epsiv/>0), where n=|V| and m=|E|. This improves significantly over the slower O/spl tilde/(min{k, n}m) exact shortest paths algorithms and a previous O/spl tilde/(mn/sup 64/t/+kn/sup 32/t/) time algorithm by Awerbuch et al. A t-spanner of a graph G is a set of weighted edges on the vertices of G such that distances in the spanner are not smaller and within a factor of t from the corresponding distances in G. Previous work was concerned with bounding the size and efficiently constructing t-spanners. We construct t-spanners of size O/spl tilde/(n/sup 1+(2+/spl epsiv///t)) in O/spl tilde/(mn/sup (2+/spl epsiv///t)) expected time (for any fixed /spl epsiv/>0), what constitutes a faster construction (by a factor of n/sup (3+2//t)) of sparser spanners than was previously attainable. We also provide efficient parallel constructions. Our algorithms are based on new structures called pairwise-covers and a novel approach to construct them efficiently.<<ETX>>