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

✍ Scribed by Paolo G. Franciosa; Giorgio Gambosi; Umberto Nanni

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 748 KB
• Volume: 61
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00202-5

✦ Synopsis

We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of arc insertions in 0( 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 O( R + m) algorithm any time a sequence of n(n) arc insertions must be handled. In particular, over a sequence of O(m) arc insertions our algorithm requires O(n) amortized time per operation, and its worst case time is 0( 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. @