@techreport{R-89-11,
TITLE = {An Efficient Parallel Algorithm for Planar Directed Reachability},
AUTHOR = {Andrzej Lingas},
YEAR = {1989},
NUMBER = {R-89-11},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-11+abstr},
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.},
IDANR = {LiTH-IDA-R-89-11}