Decremental maintenance of strongly connected components
Decremental maintenance of strongly connected components
复制标题
强连接组件的减量维护
DOI：
10.1137/1.9781611973105.82
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Roditty
中科院分区：
文献类型：
--
作者：
L. Roditty
我们考虑了n节点和M边缘的有向图的牢固连接的组件（SCC）的问题，该图形经历了一系列边缘删除序列。最近，在SODA 2011中，Lacki提出了一种确定性算法，该算法在O（MN）时间中进行了预处理，并创建了一个数据结构，该数据结构在Edge删除下保持图形删除的SCC，总更新时间为O（MN）。数据结构回答了O（1）时间中的强连接性查询。单个边删除后最坏情况的更新时间可能与O（mn）一样大。在本文中，我们减少了预处理时间和最坏情况的更新时间，即Lacki的数据结构从O（MN）到O（M log N）。查询时间和总更新时间保持不变。
We consider the problem of maintaining the strongly connected components (SCCs) of an n-nodes and m-edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, Lacki presented a deterministic algorithm that preprocess the graph in O(mn) time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of O(mn). The data structure answers strong connectivity queries in O(1) time. The worst case update time after a single edge deletion might be as large as O(mn). In this paper we reduce the preprocessing time and the worst case update time of Lacki's data structure from O(mn) to O(m log n). The query time and the total update time remain unchanged.