Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
复制标题
在分布式和流式模型中构建 (1+,ε,β)-spanner 的高效算法
DOI：
10.1145/1011767.1011791
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Jian Zhang
中科院分区：
文献类型：
--
作者：
Michael Elkin;Jian Zhang
对于一个无权重无向图\(G=(V,E)\)，以及一对正整数\(\alpha\geq1\)，\(\beta\geq0\)，一个子图\(G'=(V,H)\)，\(H\subseteq E\)，如果对于每一对顶点\(u,v\in V\)，都有\(dist_{G'}(u,v)\leq\alpha\cdot dist_{G}(u,v)+\beta\)，那么\(G'\)被称为\(G\)的一个\((\alpha,\beta)\)-生成树。在\([20]\)中表明，对于任何\(\varepsilon>0\)，\(\kappa = 1,2,\cdots\)，存在一个整数\(\beta=\beta(\varepsilon,\kappa)\)，使得对于每一个\(n\)个顶点的图\(G\)，都存在一个具有\(O(n^{1 + 1/\kappa})\)条边的\((1 + \varepsilon,\beta)\)-生成树\(G'\)。在\([18]\)中设计了一种用于构建\((1 + \varepsilon,\beta)\)-生成树的高效分布式协议。该协议的运行时间和通信复杂度分别为\(O(n^{1+\rho})\)和\(O(|E|n^{\rho})\)，其中\(\rho\)是该协议的一个额外控制参数，它只影响加法项\(\beta\)。在本文中，我们设计了一种协议，其运行时间有了极大的改进（构建\((1 + \varepsilon,\beta)\)-生成树的时间为\(O(n^{\rho})\)，而不是\([18]\)中的\(O(n^{1+\rho})\)）。我们的协议具有与\([18]\)中的协议相同的通信复杂度，并且它所构建的生成树具有与\([18]\)中的协议所构建的生成树基本相同的性质。我们还表明，我们用于构建\((1 + \varepsilon,\beta)\)-生成树的协议可以适用于流模型，并设计了一种流算法，该算法使用常数次遍历和\(O(n^{1 + 1/\kappa}\cdot\log n)\)位空间来计算所有点对的近似最短路径，其长度最多是最短路径长度乘以\((1 + \varepsilon)\)再加上\(\beta\)。我们的算法处理每条边的时间为\(O(n^{\rho})\)，对于任意小的\(\rho>0\)。之前已知的唯一解决该问题的算法\([21]\)构建的路径长度是最短路径长度的\(\kappa\)倍，具有与我们的算法相同的空间需求，但处理输入图的每条边需要\(O(n^{1 + 1/\kappa})\)时间。然而，\([21]\)中的算法对输入只使用一次遍历，而我们的算法使用常数次遍历。我们还表明，任何用于\(o(n)\)-近似距离计算的流算法都需要\(\Omega(n)\)位空间。
For an unweighted undirected graph <i>G</i>= (<i>V</i>,<i>E</i>), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph <i>G'</i>= (<i>V</i>,<i>H</i>), <i>H</i> ⊆ <i>E</i>, is called an <i>(α,β)-spanner of G</i> if for every pair of vertices <i>u</i>, <i>v</i> ∈ <i>V</i>, <i>dist<inf>G'</inf></i>(<i>u</i>,<i>v</i>) ≤ α • <i>dist<inf>G'</inf></i>(<i>u</i>,<i>v</i>) + β.It was shown in [20] that for any ε > 0, κ = 1,2, ..., there exists an integer β = β(ε,κ) such that for every <i>n</i>-vertex graph <i>G</i> there exists a (1+ε,β)-spanner <i>G'</i> with <i>O</i>(<i>n</i><sup>1+1/κ</sup>) edges. An efficient distributed protocol for constructing (1+ε,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are <i>O</i>(<i>n</i><sup>1+ρ</sup>) and <i>O</i>(|<i>E</i>|<i>n</i><sup>ρ</sup>), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (<i>O</i>(<i>n</i><sup>ρ</sup>) as opposed to (<i>O</i>(<i>n</i><sup>1+ρ</sup>) for constructing (1+ε,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+ε, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and <i>O(n</i><sup>1+1/κ</sup> • log <i>n</i>) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + ε) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time <i>O</i>(<i>n</i><sup>ρ</sup>), for an arbitrarily small ρ > <i>0</i>. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires <i>O</i>(<i>n</i><sup>1+1/κ</sup>) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for <i>o</i>(<i>n</i>)-approximate distance computation requires Ω(<i>n</i>) bits of space.