TY - GEN

T1 - Towards overcoming the transitive-closure bottleneck. Efficient parallel algorithms for planar digraphs

AU - Kao, Ming Yang

AU - Klein, Philip N.

N1 - Funding Information:
* 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.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025149855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025149855&partnerID=8YFLogxK

U2 - 10.1145/100216.100237

DO - 10.1145/100216.100237

M3 - Conference contribution

AN - SCOPUS:0025149855

SN - 0897913612

SN - 9780897913614

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 181

EP - 192

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -