(1 + εΒ)-spanner constructions for general graphs
(1 + εΒ)-spanner constructions for general graphs
复制标题
DOI：
10.1145/380752.380797
复制
发表时间：
2001-07
期刊：
影响因子：
--
通讯作者：
Michael Elkin;D. Peleg
中科院分区：
文献类型：
--
作者：
Michael Elkin;D. Peleg
图 G 的 (α,B)-spanner 是一个子图 H，使得对于每对顶点 u,w 都有 d_H(u,w)\le \cdot d_G(u,w)+&Bgr，其中 d_{G'}(u,w) 表示 G' 中两个顶点 u 和 v 之间的距离。众所周知，对于每个整数 \ge 1，每个图 G 都有一个大小为 O(n^{1+1/}) 的多项式可构造的 (2-1,0)-spanner（又名乘法 (2-1)-spanner），以及一个大小为 \tO(n^{3/2}) 的多项式可构造的 (1,2)-spanner（又名加法 2-spanner）。本文探讨了一般图的混合扳手结构（涉及乘法因子和加法因子），并表明乘法因子可以任意接近 1，同时保持扳手大小任意接近 O(n)，但代价是允许加法项成为足够大的常数。更正式地，我们证明对于任何常数 , > 0 都存在一个常数 &Bgr = &Bgr(, )，这样对于每个 n 顶点图 G 都有一个大小为 O(n^{1 + }) 的有效可构造的 (1+ , &Bgr)-spanner。由此可见，对于任何常数 , > 0，都存在一个常数 &Bgr(, )，使得对于任何 n 顶点图 G = (V,E) 都存在一个具有 O(n^{1 +}) 条边的有效可构造子图 (V,H)，使得每对顶点都有 d_H(u,w) \le (1 + ) d_G(u,w)。
An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le \cdot d_G(u,w)+&Bgr for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2-1,0)-spanner (a.k.a. multiplicative (2-1)-spanner) of size O(n^{1+1/}) for every integer \ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant , > 0 there exists a constant &Bgr = &Bgr(, ) such that for every n-vertex graph G there is an efficiently constructible (1+ , &Bgr)-spanner of size O(n^{1 + }). It follows that for any constant , > 0 there exists a constant &Bgr(, ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +}) edges such that d_H(u,w) \le (1 + ) d_G(u,w) for every pair of vertices.