Depth-First Discovery Algorithm for incremental topological sorting of directed acyclic graphs

The incremental maintenance of a Depth-F

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

✍ Paolo G. Franciosa; Giorgio Gambosi; Umberto Nanni 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 748 KB

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 DF