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 -