On the parallel complexity of digraph reachability
| Title | On the parallel complexity of digraph reachability |
| Publication Type | Journal Articles |
| Year of Publication | 1994 |
| Authors | Khuller S, Vishkin U |
| Journal | Information Processing Letters |
| Volume | 52 |
| Issue | 5 |
| Pagination | 239 - 241 |
| Date Published | 1994/12/09/ |
| ISBN Number | 0020-0190 |
| Keywords | combinatorial problems, Parallel algorithms |
| 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. |
| URL | http://www.sciencedirect.com/science/article/pii/0020019094001537 |
| DOI | 10.1016/0020-0190(94)00153-7 |