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 dire cted acyclic graph under a sequence of are insertions in O(nm) worst c ase 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 requi red to recompute DFS from scratch by using Tarjan's Theta(n + m) algor ithm any time a sequence of Omega(n) are insertions must be handled. I n particular, over a sequence of Theta(m) arc insertions our algorithm requires O(n) amortized time per operation, and its worst case time i s O(n + m). Our algorithm relies on an original characterization of a DFS-forest in terms of a relaxed planar embedding of the graph. Beside s 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 p aper provides the first solution to this problem for nontrivial classe s of graphs. (C) 1997 Elsevier Science B.V.