13
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Sep 7 '11 at 23:02
  • 3
    $\begingroup$ 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…. $\endgroup$ – Tsuyoshi Ito Sep 8 '11 at 16:41
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.