Finding and Updating Depth-First Spanning Trees of Acyclic Digraphs in Parallel
P.P. Chaudhuri · The Computer Journal · 1990
The machine model used is a parallel random access machine that allows simultaneous access to the same memory location during only the read operation. The parallel depth-first search algorithm is based on a partial spanning tree doubling technique which is found to be useful in updating the depth-first spanning tree when a new node (edge) is added to an acyclic digraph. The most notable result is an O(log n) time parallel algorithm for updating the depth-first spanning tree solution when a new node (edge) is added to an n node acyclic digraph whose depth-first spanning tree is known