Connectivity Oracles for Graphs Subject to Vertex Failures
Connectivity Oracles for Graphs Subject to Vertex Failures
复制标题
受顶点故障影响的图的连接预言
DOI：
10.1137/17m1146610
复制
发表时间：
2020
影响因子：
1.6
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Duan, Ran;Pettie, Seth
我们引入了新的数据结构来回答受批处理顶点失败影响的图中的连通性查询。确定性结构在时间上处理一批失败的顶点，然后在时间上回答连接查询。它占据空间。我们开发了数据结构的随机蒙特卡罗版本，其中包含任何故障范围的更新时间、查询时间和空间。这是第一个可以有效处理无界顶点故障的通用图连接oracle。我们还开发了一个更高效的Monte Carloedgefailure连接oracle。利用空间，及时处理边缘故障，及时回答连接查询，正确率高。我们的数据结构是基于一个新的无向图分解定理，这是一个独立的兴趣。它表明，对于任何终端集，我们可以删除一个集的顶点，使得剩余的图包含一个最大度的斯坦纳森林。
We introduce new data structures for answering connectivity queries in graphs subject to batchedvertex failures. A deterministic structure processes a batch offailed vertices intime and thereafter answers connectivity queries intime. It occupies space. We develop a randomized Monte Carlo version of our data structure with update time, query time, and spacefor any failure bound. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carloedgefailure connectivity oracle. Using space,edge failures are processed intime, and thereafter, connectivity queries are answered intime, which are correct with high probability. Our data structures are based on a new decomposition theorem for an undirected graph, which is of independent interest. It states that for any terminal setwe can remove a setofvertices such that the remaining graph contains a Steiner forest forwith maximum degree.
登录
查看更多内容
DOI：
--
发表时间：
2016
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Surender Baswana;Keerti Choudhary;L. Roditty
通讯作者：
L. Roditty
DOI：
--
发表时间：
2009
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Ran Duan;Seth Pettie
通讯作者：
Seth Pettie
动态子图连接的更快的随机最坏情况更新时间
DOI：
--
发表时间：
2016
期刊：
Workshop on Algorithms and Data Structures
影响因子：
--
作者：
Ran Duan;Le Zhang
通讯作者：
Le Zhang
DOI：
--
发表时间：
2016
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Keerti Choudhary
通讯作者：
Keerti Choudhary
DOI：
--
发表时间：
2016
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Monika Henzinger;S. Neumann
通讯作者：
S. Neumann