ECCC-Report TR20-074https://eccc.weizmann.ac.il/report/2020/074Comments and Revisions published for TR20-074en-usTue, 10 May 2022 20:02:43 +0300
Revision 3
| Depth-First Search in Directed Graphs, Revisited |
Eric Allender,
Archit Chauhan,
Samir Datta
https://eccc.weizmann.ac.il/report/2020/074#revision3We 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.Tue, 10 May 2022 20:02:43 +0300https://eccc.weizmann.ac.il/report/2020/074#revision3
Revision 2
| Depth-First Search in Directed Planar Graphs, Revisited |
Eric Allender,
Archit Chauhan,
Samir Datta
https://eccc.weizmann.ac.il/report/2020/074#revision2We 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.Wed, 15 Sep 2021 03:09:39 +0300https://eccc.weizmann.ac.il/report/2020/074#revision2
Comment 1
| Lemma 27 in the initial ECCC version is incorrect. |
Eric Allender,
Archit Chauhan,
Samir Datta
https://eccc.weizmann.ac.il/report/2020/074#comment1Lemma 27 is incorrect in the initial version of the paper is incorrect. We are posting a new version with a weaker upper bound.Sun, 11 Apr 2021 17:24:34 +0300https://eccc.weizmann.ac.il/report/2020/074#comment1
Revision 1
| Depth-First Search in Directed Graphs, Revisited |
Eric Allender,
Archit Chauhan,
Samir Datta
https://eccc.weizmann.ac.il/report/2020/074#revision1We 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.
Sun, 11 Apr 2021 13:58:34 +0300https://eccc.weizmann.ac.il/report/2020/074#revision1
Paper TR20-074
| Depth-First Search in Directed Graphs, Revisited |
Eric Allender,
Archit Chauhan,
Samir Datta
https://eccc.weizmann.ac.il/report/2020/074We 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.Wed, 06 May 2020 21:15:38 +0300https://eccc.weizmann.ac.il/report/2020/074