Algorytmy równoległe dla osiągalności w ukierunkowanych grafach płaskich

Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów . $O({\log}n)$ $O(m+n)$

Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich?

Podaj czas działania, deterministyczny / losowy algorytm i zastosowany model PRAM (zakładając, że liczba procesorów jest wielomianowa).

To pytanie dotyczy jednego z moich poprzednich pytań. Moje poprzednie pytanie dotyczy ogólnie kierowanych wykresów, które niekoniecznie są płaskie.

ds.algorithms graph-theory dc.parallel-comp

— Shiva Kintali
źródło

kliknięcie w tę iz powrotem zajęło mi zrozumienie, że różnica polega na płaskości. czy możesz to wyjaśnić, wspominając poprzednie pytanie?

— Suresh Venkat,

Zrobiłem to samo co Suresh i mogłem edytować ostatnie zdanie. Słowo „ogólne” nie jest zbyt pouczające, gdy czytelnik nie wie, z czym jest kontrastowane (w tym przypadku „planarny”). Mam nadzieję, że nie przeszkadza….

— Tsuyoshi Ito

Widzieć

Kao, Ming-Yang; Klein, Philip N. (1993), W kierunku przezwyciężenia wąskiego gardła przy zamykaniu przechodnim: wydajne algorytmy równoległe dla płaskich digrafów, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

$st$ $O(n)$ $O(\log^3 n)$

— David Eppstein
źródło