文章基本信息

标题：Depth-First Search in Directed Planar Graphs, Revisited
本地全文：下载
作者：Allender, Eric ; Chauhan, Archit ; Datta, Samir 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：202
DOI：10.4230/LIPIcs.MFCS.2021.7
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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∩co-UL), which is contained in AC². 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} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
关键词：Depth-First Search;Planar Digraphs;Parallel Algorithms;Space-Bounded Complexity Classes