Efficient Parallel Algorithms for Planar DAGs

摘要

We show that testing reachability in a planar DAG can be performed in parallel inO(log n log* n) time (0 (log n) time using randomization) using 0(n) processors. In general we give a paradigm for reducing a planar DAG to a constant size and then expanding it back. This paradigm is developed from a property of planar directed graphs we refer to as the Poincare' index formula. Using this new paradigm we then overlay our application in a fashion similar to parallel tree contraction MR85, MR89. We also discuss some of the changes needed to extend the reduction procedure to work for general planar digraphs. Using the strongly-connected components algorithm of Kao %Kao93 we can compute multiple-source reachability for general planar digraphs in 0 (log3 n) time using 0(n) processors. This improves the results of Kao and Klein KK9O who showed that this problem could be performed in O(log5 n) time using 0(n) processors. This work represents initial results of an effort to apply similar techniques to arbitrary planar directed graphs, and to develop efficient algorithms for certain problems encountered in parallel compilation. (KAR) P. 3.