An Optimal Dual Fault Tolerant Reachability Oracle
An Optimal Dual Fault Tolerant Reachability Oracle
复制标题
最优双容错可达性预言机
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Keerti Choudhary
中科院分区：
文献类型：
--
作者：
Keerti Choudhary
令 G=(V,E) 为 n 顶点 m 边有向图。令 s inV 为任何指定的源顶点。我们解决了在两个顶点失败的情况下报告 s 的可达性信息的问题。我们证明，可以在多项式时间内计算出一个 O(n) 大小的数据结构，对于任何查询顶点 v 和任何一对失败顶点 f_1、f_2，都可以在 O(1) 时间内回答 G\{f_1,f_2} 中是否存在从 s 到 v 的路径。
对于更简单的单顶点故障情况，可以使用 Lengauer 和 Tarjan 的著名作品中的支配树来获得这样的数据结构 [TOPLAS 1979，Vol. 1]。 1]。然而，过去还没有一种有效的数据结构可以处理多个故障。此外，我们还提出了一种具有 O(log^3(n)) 位大小标签的标签方案，使得对于 V 中的任何 f_1、f_2、v ，可以仅使用 f1、f_2 和 v 的标签在多对数时间内确定 v 是否可以从 G\{f_1,f_2} 中的 s 到达。
我们的数据结构也可以被视为验证双支配者的有效机制。对于 V 中的任何给定 x、y、v，我们可以在 O(1) 时间内确定 (x,y) 对是否是 v 的双支配子。早期，解决此问题的最著名方法是使用支配链，从中可以验证仅单个顶点的双支配子。
Let G=(V,E) be an n-vertices m-edges directed graph. Let s inV be any designated source vertex. We address the problem of reporting the reachability information from s under two vertex failures. We show that it is possible to compute in polynomial time an O(n) size data structure that for any query vertex v, and any pair of failed vertices f_1, f_2, answers in O(1) time whether or not there exists a path from s to v in G\{f_1,f_2}.
For the simpler case of single vertex failure such a data structure can be obtained using the dominator-tree from the celebrated work of Lengauer and Tarjan [TOPLAS 1979, Vol. 1]. However, no efficient data structure was known in the past for handling more than one failures. We, in addition, also present a labeling scheme with O(log^3(n))-bit size labels such that for any f_1, f_2, v in V , it is possible to determine in poly-logarithmic time if v is reachable from s in G\{f_1,f_2} using only the labels of f1, f_2 and v.
Our data structure can also be seen as an efficient mechanism for verifying double-dominators. For any given x, y, v in V we can determine in O(1) time if the pair (x,y) is a double-dominator of v. Earlier the best known method for this problem was using dominator chain from which verification of double-dominators of only a single vertex was possible.