Dynamic DFS Tree in Undirected Graphs: breaking the $O(m)$ barrier

Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary +1

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given u…