@inproceedings{e0c4131917fa4c9e828ed4bbf0a3f922,

title = "Parallel depth-first search in general directed graphs",

abstract = "A directed cyle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the problem of finding a directed cycle separator is in randomized NC. The paper also proves that computing cycle separators and conducting depth-first search in directed graphs are deterministic NC-equivalent. These two results together yield the first RNC algorithm for depth-first search in directed graphs.",

author = "Alok Aggarwal and Anderson, {Richard J.} and Kao, {Ming Yang}",

year = "1989",

doi = "10.1145/73007.73035",

language = "English (US)",

isbn = "0897913078",

series = "Proc Twenty First Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "297--308",

booktitle = "Proc Twenty First Annu ACM Symp Theory Comput",

note = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing ; Conference date: 15-05-1989 Through 17-05-1989",

}