Algoritmos paralelos para acessibilidade em gráficos planares direcionados

13

Chong, Han e Lam mostraram que a conectividade st não direcionada pode ser resolvida no EREW PRAM em time com processadores .O(registron)O(m+n)

Qual é o algoritmo paralelo mais conhecido para conectividade st em gráficos planares direcionados?

Indique o tempo de execução, o algoritmo determinístico / aleatório e o modelo PRAM usado (assumindo que o número de processadores seja polinomial).

Esta pergunta está relacionada a uma das minhas perguntas anteriores. Minha pergunta anterior é sobre gráficos direcionados gerais que não são necessariamente planares.

ds.algorithms graph-theory dc.parallel-comp Shiva Kintali
fonte
4
levei alguns cliques para perceber que a diferença era planaridade. você pode esclarecer isso quando menciona a pergunta anterior?
Suresh Venkat
3
Fiz o mesmo que Suresh e tomei a liberdade de editar a última frase. A palavra "geral" não é muito informativa quando o leitor não sabe com o que é contrastado ("planar" neste caso). Eu espero que você não se importe….
Tsuyoshi Ito

Respostas:

3

Vejo

  • Kao, Ming-Yang; Klein, Philip N. (1993), Para superar o gargalo de fechamento transitivo: algoritmos paralelos eficientes para dígrafos planares, J. Comput. Sci do sistema 47 (1993), n. 3, 459–500.

stO(n)O(registro3⁡n)

David Eppstein
fonte