论文标题
用于几乎最佳顶点容错跨度的多项式时间算法
A Polynomial Time Algorithm for Almost Optimal Vertex Fault Tolerant Spanners
论文作者
论文摘要
我们介绍了第一个多项式时间算法，用于f顶点容差启动器问题，该问题几乎达到了最佳的扳手大小。我们用于构建F顶点容射扳手的算法取$ O（K \ CDOT N \ CDOT M^2 \ CDOT W）$ time，其中W是最大边缘重量，并构造了大小$ O（N^{1+1/K} F^{1+1/K} f^{1-1/K} {1-1/k} \ cdot（1+1/k} \ cdot（\ cdot n）^1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1。我们的扳手几乎具有最佳的尺寸，最多是最差的案例尺寸上的上限。在这项工作之前，没有其他多项式时间算法因构建具有最佳尺寸的F顶点耐受性跨度而闻名。 我们的算法基于首先贪婪地构建了一个击球集，用于收集重量的重量路径，最多是$ k \ cdot w（u，v）$之间的边缘u和v（u，v）之间，然后使用此组来决定是否需要将边缘（u，v）添加到增长的范围中。
We present the first polynomial time algorithm for the f vertex fault tolerant spanner problem, which achieves almost optimal spanner size. Our algorithm for constructing f vertex fault tolerant spanner takes $O(k\cdot n\cdot m^2 \cdot W)$ time, where W is the maximum edge weight, and constructs a spanner of size $O(n^{1+1/k}f^{1-1/k}\cdot (\log n)^{1-1/k})$. Our spanner has almost optimal size and is at most a $\log n$ factor away from the upper bound on the worst-case size. Prior to this work, no other polynomial time algorithm was known for constructing f vertex fault tolerant spanner with optimal size. Our algorithm is based on first greedily constructing a hitting set for the collection of paths of weight at most $k \cdot w(u,v)$ between the endpoints u and v of an edge (u,v) and then using this set to decide whether the edge (u,v) needs to be added to the growing spanner.
