Parallel depth-first search in general directed graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)397-409
Number of pages13
JournalSIAM Journal on Computing
Volume19
Issue number2
DOIs
StatePublished - Jan 1 1990

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

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

Cite this