Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs
M.-Y. Kao, Philip N. Klein · 1990
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 techniques in parallel algorithms for digraph reachability.To pinpoint the nature of the bottleneck, we de* velop 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.