Incremental DFS Trees on Arbitrary Directed Graphs

Giorgio Ausiello, Paolo G. Franciosa, Giuseppe F. Italiano +1

We present a new algorithm for maintaining a DFS tree of an arbitrary directed graph under any sequence of edge insertions. Our algorithm requires a total of $O(m\cdot n)$ time in…