Abstract
Currently, there is a significant gap between the best sequential and parallel complexities of many fundamental problems related to digraph reachability. This complexity bottleneck essentially reflects a seemingly unavoidable reliance on transitive closure techiques in parallel algorithms for digraph reachability. To pinpoint the nature of the bottleneck, we develop a collection of polylog-time reductions among reachability problems. These reductions use only linear processors and work for general graphs. Furthermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendent counting, and (5) depth-first search. These algorithms use only linear processors and therefore reduce the complexity to within a polylog factor of optimal.
| Original language | English (US) |
|---|---|
| Title of host publication | Proc 22nd Annu ACM Symp Theory Comput |
| Publisher | Publ by ACM |
| Pages | 181-192 |
| Number of pages | 12 |
| ISBN (Print) | 0897913612, 9780897913614 |
| DOIs | |
| State | Published - 1990 |
| Event | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990 |
Publication series
| Name | Proc 22nd Annu ACM Symp Theory Comput |
|---|
Other
| Other | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing |
|---|---|
| City | Baltimore, MD, USA |
| Period | 5/14/90 → 5/16/90 |
Funding
* Research supported in part by NSF Grant CCR-8909323. + Research supported in part by ONR Grant NOOO14-88-K-0243 and DARPA Grant NOtXl39-88-C0113. Most of this work was done while he was at Aiken Computation Laboratory, Harvard University.
ASJC Scopus subject areas
- General Engineering