Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs
Shahbaz Khan · 2017
Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical algorithm [SIAMCOMP74] for building a DFS tree requires O(m+n) time for a given undirected graph G having n vertices and m edges. Recently, Baswana et al. [SODA16] presented a simple algorithm for updating the DFS tree of an undirected graph after an edge/vertex update in O (n) time. However, their algorithm is strictly sequential. We present an algorithm achieving similar bounds, that can be adopted easily to the parallel environment. In the parallel environment, a DFS tree can be computed from scratch using O(m) processors in expected O (1) time [SICOMP90] on an EREW PRAM, whereas the best deterministic algorithm takes O (√n) time [SIAMCOMP90,JAL93] on a CRCW PRAM. Our algorithm can be used to develop optimal (upto polylog n factors) deterministic algorithms for maintaining fully dynamic DFS and fault tolerant DFS, of an undirected graph.