Depth-first search in directed planar graphs, revisited
Depth-first search in directed planar graphs, revisited
复制标题
重新审视有向平面图中的深度优先搜索
DOI：
10.1007/s00236-022-00425-1
复制
发表时间：
2022
期刊：
影响因子：
0.6
通讯作者：
Datta, Samir
中科院分区：
文献类型：
--
作者：
Allender, Eric;Chauhan, Archit;Datta, Samir
我们给出了一种构造平面有向图中深度优先搜索树的算法，该算法可以在复杂类中实现，该类包含在。在此之前(超过四分之一个世纪)，该问题的最快一致确定性并行算法的运行时间为(对应于复杂性类)。我们还考虑了在其他图类中计算深度优先搜索树的问题，得到了额外的新的上界。
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class, which is contained in. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem had a runtime of(corresponding to the complexity class). We also consider the problem of computing depth-first search trees in other classes of graphs and obtain additional new upper bounds.
登录
查看更多内容
通过电路分离顶点
DOI：
10.1016/0012-365x(75)90032-1
发表时间：
1975
期刊：
Discret. Math.
影响因子：
--
作者：
W. T. Tutte
通讯作者：
W. T. Tutte
DOI：
--
发表时间：
1997
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Klaus
通讯作者：
Klaus
对数交替层次结构崩溃：AΣ2L = A∏2L
影响因子：
1
作者：
Birgit Jenner;Bernd Kirsig;Klaus
通讯作者：
Klaus
格林定理和平面图中的孤立
DOI：
10.1016/j.ic.2012.03.002
发表时间：
2012
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Raghunath Tewari;N. V. Vinodchandran
通讯作者：
N. V. Vinodchandran
对数交替层次结构崩溃：Aσ L -2- = AP L -2-
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
Klaus;Birgit Jenner;Bernd Kirsig
通讯作者：
Bernd Kirsig