Let G = (V, E) be a strongly connected directed graph. Start with the graph G' = (V, {}). We are given a list L of edges in E such that every edge in L we add to G' (in order) connects two strongly connected components. What's a fast algorithm to keep track of the strongly connected components of G' as we add one edge at a time? Using Kosaraju's or Tarjan's algorithm at every step takes O(|E|(|V|+|E|)) time, which I'm guessing can be improved.
Asked
Active
Viewed 276 times
2
-
1This looks like the state of the art: https://arxiv.org/pdf/1105.2397.pdf – David Eisenstat Mar 18 '19 at 23:02
-
1Or maybe this: https://arxiv.org/pdf/1112.0784.pdf – David Eisenstat Mar 18 '19 at 23:03