Accession Number : ADA297035

Title :   Efficient Parallel Algorithms for Planar DAGs,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s) : Guattery, Stephen ; Miller, Gary L.

PDF Url : ADA297035

Report Date : MAY 1995

Pagination or Media Count : 65

Abstract : We show that testing reachability in a planar DAG can be performed in parallel in O(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

Descriptors :   *ALGORITHMS, *GRAPHS, *PARALLEL PROCESSING, COMPUTATIONS, SIZES(DIMENSIONS), FORMULATIONS, EFFICIENCY, REDUCTION, INDEXES.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE