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.

Improve this question
$\endgroup$
2
  • 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, 2011 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, 2011 at 16:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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