We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC2 Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log10 (corresponding to the complexity class AC10 ? NC11 We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds. 2012 ACM Subject Classification Complexity Classes, Parallel Algorithms.
展开▼
