Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-074 | 6th May 2020 21:14

Depth-First Search in Directed Graphs, Revisited



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.

ISSN 1433-8092 | Imprint