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 NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10, which is contained in NC^11).
We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
Added some figures and some clarifications
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 NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10, which is contained in NC^11).
We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
The title has changed. More details and clarifications are provided in several places.
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL intersect co-UL), which is contained in AC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10, which is contained in NC^11).
We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
The upper bound is weaker; there was an error in Lemmma 27 of the previous version.
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 NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10, which is contained in NC^11).
We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
Lemma 27 is incorrect in the initial version of the paper is incorrect. We are posting a new version with a weaker upper bound.
