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 ( m + n ) .$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.

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)$