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

Abstract

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
Volume52
Issue number5
DOIs
StatePublished - Dec 9 1994

Keywords

  • Combinatorial problems
  • Parallel algorithms

ASJC Scopus subject areas

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

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

Cite this