期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-19
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm 16 can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC2 17 . Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log10 18 n) (corresponding to the complexity class AC10 ⊆ NC11 19 ). 20 We also consider the problem of computing depth-first search trees in other classes of graphs, 21 and obtain additional new upper bounds.
