Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
复制标题
多项式时间内最优顶点容错扳手
DOI：
10.1137/1.9781611976465.174
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Robelle, Caleb
中科院分区：
文献类型：
--
作者：
Bodwin, Greg;Dinitz, Michael;Robelle, Caleb
最近的工作已经确定了顶点容错空间的存在最优大小界限：对于任何正整数k，每个n-节点图都有一个（2k- 1）-n-0（f1-1/kn 1 +1/k）条边能抵抗顶点故障，并且有一些输入图的例子不能改进这个界限。然而，这些证明是通过分析某个指数时间贪婪算法的输出来工作的。在这项工作中，我们给出了第一个算法，产生顶点容错空间的最佳大小和运行在多项式时间。具体地说，我们给出了一个随机化算法，该算法需要（f1-1/kn 2 +1/k+ mf 2）时间。我们也去随机化我们的算法，给出一个确定性的算法与类似的界限。这反映了在运行时间上的指数级改进[Bodwin-Patel PODC '19]，这是以前唯一已知的用于构建最佳顶点容错spectrometer的算法。
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integerk, everyn-node graph has a (2k– 1)-spanner onO(f1–1/kn1+1/k) edges resilient tofvertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takesÕ(f1–1/kn2+1/k+mf2) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.
登录
查看更多内容
最佳顶点容错扳手（用于固定拉伸）
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Gregory Bodwin;M. Dinitz;M. Parter;V. V. Williams
通讯作者：
V. V. Williams
DOI：
--
发表时间：
1993
期刊：
Annual International Cryptology Conference
影响因子：
--
作者：
Richard Taylor
通讯作者：
Richard Taylor
DOI：
--
发表时间：
2019
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
M. Parter
通讯作者：
M. Parter
DOI：
--
发表时间：
1990
期刊：
Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Awerbuch;D. Peleg
通讯作者：
D. Peleg
顶点容错 Spanner 的一个简单但最佳的解决方案
DOI：
--
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Gregory Bodwin;Shyamal Patel
通讯作者：
Shyamal Patel