Name
Abstract | ||
|---|---|---|
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class
$$\text{ AC}^1(\text{ UL }\cap \text{ co-UL})$$
, which is contained in
$$\text{ AC}^2$$
. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem had a runtime of
$$O(\log ^{10}n)$$
(corresponding to the complexity class
$$\text{ AC}^{10}\subseteq \text{ NC}^{11}$$
). We also consider the problem of computing depth-first search trees in other classes of graphs and obtain additional new upper bounds.
|
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00236-022-00425-1 | Acta Informatica |
DocType | Volume | Issue |
Journal | 59 | 4 |
ISSN | Citations | PageRank |
0001-5903 | 0 | 0.34 |
References | Authors | |
22 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| Archit Chauhan | 2 | 0 | 0.34 |
| Samir Datta | 3 | 200 | 19.82 |