Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR20-074 | 15th September 2021 03:09

Depth-First Search in Directed Planar Graphs, Revisited

RSS-Feed




Revision #2
Authors: Eric Allender, Archit Chauhan, Samir Datta
Accepted on: 15th September 2021 03:09
Downloads: 8
Keywords: 


Abstract:

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.



Changes to previous version:

The title has changed. More details and clarifications are provided in several places.


Revision #1 to TR20-074 | 11th April 2021 13:58

Depth-First Search in Directed Graphs, Revisited





Revision #1
Authors: Eric Allender, Archit Chauhan, Samir Datta
Accepted on: 11th April 2021 13:58
Downloads: 86
Keywords: 


Abstract:

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.



Changes to previous version:

The upper bound is weaker; there was an error in Lemmma 27 of the previous version.


Paper:

TR20-074 | 6th May 2020 21:14

Depth-First Search in Directed Graphs, Revisited


Abstract:

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.


Comment(s):

Comment #1 to TR20-074 | 11th April 2021 17:24

Lemma 27 in the initial ECCC version is incorrect.

Authors: Eric Allender, Archit Chauhan, Samir Datta
Accepted on: 11th April 2021 17:24
Keywords: 


Comment:

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




ISSN 1433-8092 | Imprint