Revision #3 Authors: Eric Allender, Archit Chauhan, Samir Datta

Accepted on: 10th May 2022 20:02

Downloads: 60

Keywords:

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

Revision #2 Authors: Eric Allender, Archit Chauhan, Samir Datta

Accepted on: 15th September 2021 03:09

Downloads: 120

Keywords:

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.

Revision #1 Authors: Eric Allender, Archit Chauhan, Samir Datta

Accepted on: 11th April 2021 13:58

Downloads: 354

Keywords:

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.

TR20-074 Authors: Eric Allender, Archit Chauhan, Samir Datta

Publication: 6th May 2020 21:15

Downloads: 801

Keywords:

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).

Lemma 27 is incorrect in the initial version of the paper is incorrect. We are posting a new version with a weaker upper bound.