ACM Transactions on Algorithms · 2013 · 47 citations · 13 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsConnected Components MaintenanceLas Vegas AlgorithmsPlanar GraphsReachabilityReachability AnalysisStrongly Connected ComponentsTransitive Closure
This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O ( mn ) time and answers queries in constant time. Previously, such time bound has only been achieved by a randomized Las Vegas algorithm. In addition to that, a few decremental algorithms for maintaining strongly connected components are shown, whose time complexity is O ( n 1.5 ) for planar graphs, O ( n log n ) for graphs with bounded treewidth and O ( mn ) for general digraphs.
13
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Introduction to algorithms [2nd ed.]
Thomas H. Cormen · 2001 · 1.9K citations
A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Applied Mathematics · 1979 · 1.4K citations
Finding approximate separators and computing tree width quickly
Bruce A. Reed · 1992 · 178 citations · Full text