The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs

We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of are insertions in O(nm) worst case total time, where n is the number of nodes and m is the number of arcs after the insertions. This compares favorably with the time required to recompute DFS from scratch by using Tarjan's Theta(n + m) algorithm any time a sequence of Omega(n) are insertions must be handled. In particular, over a sequence of Theta(m) arc insertions our algorithm requires O(n) amortized time per operation, and its worst case time is O(n + m). Our algorithm relies on an original characterization of a DFS-forest in terms of a relaxed planar embedding of the graph. Besides the basic representation of the graphs in term of adjacency lists, O(n) additional space is required. Although the problem of the dynamic maintenance of a DFS-tree was pointed out about one decade ago, this paper provides the first solution to this problem for nontrivial classes of graphs. (C) 1997 Elsevier Science B.V.