Incremental DFS algorithms: a theoretical and experimental study

Surender Baswana, Ayush Goel, Shahbaz Khan

Depth First Search (DFS) tree is a fundamental data structure for solving graph problems. The DFS tree of a graph $G$ with $n$ vertices and $m$ edges can be built in $O(m+n)$ time.…