Efficient algorithms for constructing fault-tolerant geometric spanners
Efficient algorithms for constructing fault-tolerant geometric spanners
复制标题
构建容错几何扳手的高效算法
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Smid
中科院分区：
文献类型：
--
作者：
C. Levcopoulos;G. Narasimhan;M. Smid
设\(S\)是\(\mathbb{R}^d\)中的\(n\)个点的集合，\(k\)是一个整数，满足\(1\leq k\leq\frac{n}{2}\)。给出了为\(S\)构造容错生成树的算法。如果在这样的生成树中最多移除\(k\)条边或顶点，那么剩余图中的每对点仍然通过一条短路径相连。我们的结果包括：（i）一个运行时间为\(O(n\log_d^{\beta_1}n + kn\log\log n + k^2n)\)的算法，它构造一个具有\(O(k^2n)\)条边的生成树，该生成树对\(k\)条边故障有弹性；（ii）一个运行时间为\(O(n\log n + k^2n)\)的算法，它构造一个具有\(O(k^2n)\)条边的生成树，该生成树对\(k\)个顶点故障有弹性；（iii）一个运行时间为\(O(n\log n + \xi n)\)的算法，它构造一个度为\(O(s)\)的生成树，其总边长由\(G(2)\)乘以\(S\)的最小生成树的权重界定，并且对\(k\)条边或顶点故障有弹性。这里，\(c\)是一个与\(n\)和\(k\)无关的常数。
Let S be a set of n points in lKd, and k m integer such that 1 5 k 5 n 2. Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path. Our results include (i) an algorithm with running time O(n logdB1 n + kn log log n + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n logn + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with rllnning time O(n logn+&n) that constructs a spanner of degree O(s), whose total edge length is bounded by G(2) times the weight of a miuimum spanning tree of S, and that is resilient to k edge or vertex faults. Here, c is a constant that is independent of n and Ic.