Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
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.
Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Eric Price, David P. Woodruff
FOCS 2011
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009