LINEAR-PROCESSOR NC ALGORITHMS FOR PLANAR DIRECTED-GRAPHS .2. DIRECTED SPANNING-TREES

It is a fundamental open problem whether polylogarithmic time and a li near number of processors are sufficient for computing the strongly co nnected components of a directed graph and constructing directed spann ing trees for these components. This paper provides the first nontrivi al partial solution to the tree problem: for a strongly connected plan ar directed graph of size n a directed spanning tree rooted at a speci fied vertex can be computed in O(log2n) time with n/ log n processors. This result complements an algorithm by Kao that computes the strongl y connected components of a planar directed graph in O(log3n) time wit h n/log n processors. Both algorithms run on a deterministic parallel random-access machine that permits concurrent reads and concurrent wri tes in its shared memory and, in case of a write conflict, allows an a rbitrary processor to succeed.