M.F. Cowlishaw
IBM Systems Journal
A directed cycle separator of an n-vertex directed graph is a vertex-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. It is shown that the problem of finding a directed cycle separator is in randomized NC. It is also proved that computing cycle separators and conducting depth-first search in directed graphs are deterministically NC-equivalent. These two results together yield the first randomized NC algorithm for depth-first search in general directed graphs.
M.F. Cowlishaw
IBM Systems Journal
Fan Zhang, Junwei Cao, et al.
IEEE TETC
G. Ramalingam
Theoretical Computer Science
Liqun Chen, Matthias Enzmann, et al.
FC 2005