Parallel depth-first search in general directed graphs

Alok Aggarwal*, Richard J. Anderson, Ming Yang Kao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProc Twenty First Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages297-308
Number of pages12
ISBN (Print)0897913078, 9780897913072
DOIs
StatePublished - 1989
EventProceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA
Duration: May 15 1989May 17 1989

Publication series

NameProc Twenty First Annu ACM Symp Theory Comput

Other

OtherProceedings of the Twenty First Annual ACM Symposium on Theory of Computing
CitySeattle, WA, USA
Period5/15/895/17/89

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Parallel depth-first search in general directed graphs'. Together they form a unique fingerprint.

Cite this