On the parallel complexity of digraph reachability

TitleOn the parallel complexity of digraph reachability
Publication TypeJournal Articles
Year of Publication1994
AuthorsKhuller S, Vishkin U
JournalInformation Processing Letters
Pagination239 - 241
Date Published1994/12/09/
ISBN Number0020-0190
Keywordscombinatorial problems, Parallel algorithms

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.