About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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.