My. Kao et Ge. Shannon, LINEAR-PROCESSOR NC ALGORITHMS FOR PLANAR DIRECTED-GRAPHS .2. DIRECTED SPANNING-TREES, SIAM journal on computing, 22(3), 1993, pp. 460-481
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.