Algoritmos paralelos para la accesibilidad en gráficos planos dirigidos

Chong, Han y Lam mostraron que la conectividad st no dirigida se puede resolver en la EREW PRAM en tiempo con procesadores . $O({\log}n)$ $O(m+n)$

¿Cuál es el algoritmo paralelo más conocido para la conectividad st en gráficos planos dirigidos?

Indique el tiempo de ejecución, el algoritmo determinista / aleatorio y el modelo PRAM utilizado (suponiendo que el número de procesadores es polinómico).

Esta pregunta está relacionada con una de mis preguntas anteriores. Mi pregunta anterior es sobre gráficos generales dirigidos que no son necesariamente planos.

ds.algorithms graph-theory dc.parallel-comp Shiva Kintali
fuente

Me tomó un poco de tiempo darme cuenta de que la diferencia era la planaridad. ¿Puedes aclarar eso cuando mencionas la pregunta anterior?

Suresh Venkat

Hice lo mismo que Suresh, y me tomé la libertad de editar la última oración. La palabra "general" no es muy informativa cuando el lector no sabe a qué se compara ("planar" en este caso). Espero que no te importe….

Tsuyoshi Ito

Respuestas:

Ver

Kao, Ming-Yang; Klein, Philip N. (1993), Hacia la superación del cuello de botella del cierre transitivo: algoritmos paralelos eficientes para dígrafos planos, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

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

David Eppstein
fuente