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

## IDA Technical Reports: abstract

*Generated: Thu, 27 Nov 2014 14:08:51 *

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
```

*<webmaster@ida.liu.se>*