Параллельные алгоритмы достижимости в направленных плоских графах

Чонг, Хан и Лэм показали, что ненаправленное соединение через st-соединение может быть решено с помощью EREW PRAM за с помощью O ( m + n ) процессоров.$O({\log}n)$$O(m+n)$

Каков наиболее известный параллельный алгоритм для st-связности в направленных плоских графах?

Пожалуйста, укажите время работы, детерминированный / рандомизированный алгоритм и используемую модель PRAM (предполагая, что число процессоров является полиномиальным).

Этот вопрос связан с одним из моих предыдущих вопросов. Мой предыдущий вопрос касается общих ориентированных графов, которые не обязательно являются плоскими.

Видеть

• Као, Мин-Ян; Klein, Philip N. (1993). К преодолению узкого места транзитивного замыкания: эффективные параллельные алгоритмы для плоских орграфов, J. Comput. System Sci. 47 (1993), нет. 3, 459–500.

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