Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
复制标题
有向图递减单源可达性的改进算法
DOI：
10.1007/978-3-662-47672-7_59
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Danupon Nanongkai
中科院分区：
文献类型：
--
作者：
Monika Henzinger;Sebastian Krinninger;Danupon Nanongkai
最近，我们提出了第一种算法，用于维护有向图中从源节点可达的节点集，该有向图通过删除边修改，总更新时间为\(o(mn)\)，其中\(m\)是边的数量，\(n\)是图中的节点数量[Henzinger等人]。[2014]。该算法是几种不同算法的组合，每种算法都有不同的\(m\)与\(n\)权衡。对于\(m = \varTheta (n^{1.5})\)，运行时间为\(O(n^{2.47})\)，略低于\(mn = \varTheta (n^{2.5})\)。本文采用新的算法思想对原有算法进行了简化，提高了\(\tilde{O}(\min ( m^{7/6} n^{2/3}, m^{3/4} n^{5/4 + o(1)}, m^{2/3} n^{4/3+o(1)} + m^{3/7} n^{12/7+o(1)}))\)的运行时间。例如，对于臭名昭著的案例\(m = \varTheta (n^{1.5})\)，这给出\(O(n^{2.36})\)。对于有向图的强连通分量的维持问题，我们得到了相同的上界。我们的算法在对付健忘的对手时很有可能是正确的。
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with \(o(mn)\) total update time, where \(m\) is the number of edges and \(n\) is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different \(m\) vs. \(n\) trade-off. For the case of \(m = \varTheta (n^{1.5})\) the running time is \(O(n^{2.47})\), just barely below \(mn = \varTheta (n^{2.5})\). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of \(\tilde{O}(\min ( m^{7/6} n^{2/3}, m^{3/4} n^{5/4 + o(1)}, m^{2/3} n^{4/3+o(1)} + m^{3/7} n^{12/7+o(1)}))\). This gives, e.g., \(O(n^{2.36})\) for the notorious case \(m = \varTheta (n^{1.5})\). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.