%0 Journal Article
%T Incremental DFS Trees on Arbitrary Directed Graphs
%A Giorgio Ausiello
%A Paolo G. Franciosa
%A Giuseppe F. Italiano
%A Andrea Ribichini
%J Computer Science
%D 2015
%I arXiv
%X 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 the worst case to process a sequence of edge insertions, where $n$ is the number of vertices in the graph and $m$ is the total number of edges in the final graph. We also prove lower bounds for variations of this problem.
%U http://arxiv.org/abs/1502.07206v2