Decremental strongly-connected components and single-source reachability in near-linear time

Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff‐Nilsen

2019 · 28 citations · 19 references

Concepts

Abstract

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.

References

19