Dual-failure distance and connectivity oracles
Dual-failure distance and connectivity oracles
复制标题
双故障距离和连接预言
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Seth Pettie
中科院分区：
文献类型：
--
作者：
Ran Duan;Seth Pettie
自发故障是所有网络的不可避免的方面，尤其是那些具有物理基础的网络，例如通信网络或道路网络。无论是由于恶意协调的攻击还是其他原因，失败都会暂时改变网络的拓扑，并因此而改变其连通性和距离指标。在本文中，我们研究了在存在两个节点或链接失败的情况下有效回答连接性，距离和最短路由查询的问题。我们的数据结构使用O（n2）空间，并在O（1）时间中答案查询，该查询位于最佳的聚类因子之内，几乎与Demestrescu等人的单次失败距离隔离匹配。可能还可以找到能够处理任何固定数量故障的距离/连接性甲骨文。但是，我们算法的纯粹复杂性表明，超越双重失败将需要对该问题产生根本不同的方法。
Spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks. Whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its connectivity and distance metric. In this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of two node or link failures. Our data structure uses O(n2) space and answers queries in O (1) time, which is within a polylogarithmic factor of optimal and nearly matches the single-failure distance oracles of Demestrescu et al. It may yet be possible to find distance/connectivity oracles capable of handling any fixed number of failures. However, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.