13

Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.

What is the best known parallel algorithm for st-connectivity in directed planar graphs ?

Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial).

This question is related to one of my previous questions. My previous question is about general directed graphs which are not necessarily planar.

Community
  • 1
Shiva Kintali
  • 10,578
  • 41
  • 74
  • 4
    it took me some clicking back and forth to realize that the difference was planarity. can you clarify that when you mention the previous question ? – Suresh Venkat Sep 07 '11 at 23:02
  • 3
    I did the same thing as Suresh, and I took the liberty of editing the last sentence. The word “general” is not very informative when the reader does not know what it is contrasted to (“planar” in this case). I hope you do not mind…. – Tsuyoshi Ito Sep 08 '11 at 16:41

1 Answers1

3

See

  • Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google scholar for other papers that cited theirs, I didn't see anyone else with improvements to this.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278