@article {15214,
title = {On the parallel complexity of digraph reachability},
journal = {Information Processing Letters},
volume = {52},
year = {1994},
month = {1994/12/09/},
pages = {239 - 241},
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.},
keywords = {combinatorial problems, Parallel algorithms},
isbn = {0020-0190},
doi = {10.1016/0020-0190(94)00153-7},
url = {http://www.sciencedirect.com/science/article/pii/0020019094001537},
author = {Khuller, Samir and Vishkin, Uzi}
}