IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Wed, 18 Oct 2017 00:31:54

Lingas, A. (1989). An Efficient Parallel Algorithm for Planar Directed Reachability. Technical Report LiTH-IDA-R-89-11, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: We present a preprocessing of planar digraphs which enables us to solve all the reachability problems for a distinguished vertex of a planar digraph in time O((log n)**2) using a CREW PRAM with O(n log n) processors. The preprocessing takes O((log n)**6) time using a CRCW PRAM with O((n**1.5)(log n)**2) processors. Employing it, we can find the transitive closure of a planar digraph in time O((log n)**6) using a CRCW PRAM with O((n**2)log n) processors.

Goto (at Linköping University): CS Dept TR Overview