2019 · 28 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryTheory Of ComputationApproximation AlgorithmsComputational ComplexityDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsConditional Lower BoundsDynamic Graph AlgorithmsFully Dynamic Graph AlgorithmsLower BoundsPlanar Graph AlgorithmsReachabilityStrongly Connected Components
Computing the Strongly-Connected Components (SCCs) in a graph G=(V,E) is known to take only O(m+n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = |E|, n=|V|. For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e. graphs that undergo edge deletions.
19
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
An On-Line Edge-Deletion Problem
Yossi Shiloach, Shimon Even · Journal of the ACM · 1981 · 284 citations
A new approach to dynamic all pairs shortest paths
Camil Demetrescu, Giuseppe F. Italiano · Journal of the ACM · 2004 · 270 citations