Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
复制标题
动态子图连接的更快的随机最坏情况更新时间
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Le Zhang
中科院分区：
文献类型：
--
作者：
Ran Duan;Le Zhang
现实世界的网络很容易崩溃。通常在底层图G中，除了插入或删除边之外，活动顶点的集合还会随着时间的推移而变化。一个顶点可能主动工作，也可能失败，暂时被隔离。动态子图连通性回答了由S引起的G子图中任意两个活动顶点之间的连通性查询，该问题通过支持更新和回答连通性查询的动态数据结构来解决。在一般无向图中，我们提出了一种随机化的数据结构，其最坏情况更新时间为\(\widetilde{O}(m^{3/4})\)。前者的最佳结果包括\(\widetilde{O}(m^{2/3})\)确定性平摊更新时间由Chan， Pǎtrascu和Roditty [4]， \(\widetilde{O}(m^{4/5})\)由Duan[8]和\(\widetilde{O}(\sqrt{mn})\)由Baswana， Chaudhury， Choudhary和Khan[2]确定性最坏情况更新时间。
Real-world networks are prone to breakdowns. Typically in the underlying graph G, besides the insertion or deletion of edges, the set of active vertices changes overtime. A vertex might work actively, or it might fail, and gets isolated temporarily. The active vertices are grouped as a set S. The set S is subjected to updates, i.e., a failed vertex restarts, or an active vertex fails, and gets deleted from S. Dynamic subgraph connectivity answers the queries on connectivity between any two active vertices in the subgraph of G induced by S. The problem is solved by a dynamic data structure, which supports the updates and answers the connectivity queries. In the general undirected graph, we propose a randomized data structure, which has \(\widetilde{O}(m^{3/4})\) worst-case update time. The former best results for it include \(\widetilde{O}(m^{2/3})\) deterministic amortized update time by Chan, Pǎtrascu and Roditty [4], \(\widetilde{O}(m^{4/5})\) by Duan [8] and \(\widetilde{O}(\sqrt{mn})\) by Baswana, Chaudhury, Choudhary and Khan [2] deterministic worst-case update time.