Finding and Updating Depth-First Spanning Trees of Acyclic Digraphs in Parallel

Open Access
Publisher Website
Google Scholar
Abstract
Fast parallel algorithms are presented for finding and updating the depth-first spanning tree of an acyclic digraph. 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.

This publication has 0 references indexed in Scilit: