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

• Published in: Information processing letters 1997-01, Vol.61 (2), p.113-120
• Main Authors: Franciosa, Paolo G., Gambosi, Giorgio, Nanni, Umberto
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Analysis of algorithms; Applied sciences; Computer science; Computer science; control theory; systems; Decision trees; Depth-first search; Design of algorithms; Exact sciences and technology; Graphs; Information processing; Information retrieval. Graph; Studies; Theoretical computing; Theory
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/S0020-0190(96)00202-5

We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of arc 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 Θ( n + m) algorithm any time a sequence of Ω(n) arc insertions must be handled. In particular, over a sequence of Θ( 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.