Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
Ming‐Yang Kao, Gregory E. Shannon · SIAM Journal on Computing · 1993
It is a fundamental open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components of a directed graph and constructing directed spanning trees for these components. This paper provides the first nontrivial partial solution to the tree problem: for a strongly connected planar directed graph of size n a directed spanning tree rooted at a specified vertex can be computed in $O(\log ^2 n)$ time with ${n / {\log n}}$ processors. This result complements an algorithm by Kao that computes the strongly connected components of a planar directed graph in $O(\log ^3 n)$ time with ${n / {\log n}}$ processors. Both algorithms run on a deterministic parallel random-access machine that permits concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, allows an arbitrary processor to succeed.