Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs
Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs
Depth first search (DFS) tree is a fundamental data structure for solving graph problems. The classical algorithm [SiComp74] for building a DFS tree requires $O(m+n)$ time for a given graph $G$ having $n$ vertices and $m$ edges. Recently, Baswana et al. [SODA16] presented a simple algorithm for updating DFS tree …