On the parallel complexity of digraph reachability

Samir Khuller*, Uzi Vishkin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.

Original languageEnglish (US)
Pages (from-to)239-241
Number of pages3
JournalInformation Processing Letters
Issue number5
StatePublished - Dec 9 1994


  • Combinatorial problems
  • Parallel algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'On the parallel complexity of digraph reachability'. Together they form a unique fingerprint.

Cite this