Algortimos Paralelos para Árvores Geradoras e Componentes Conexos - Cáceres, Edson Norberto (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1992: Anais do IV Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1992)
Dado um grafo G = (V, E) com n vértices em arestas, apresentamos uma implementação simples em uma CREW PRAM de algoritmos paralelos para computação da árvore geradora e dos componentes conexos de um grafo. Os algoritmos são executados em tempo paralelo O(log 2 n) com m/log n processadores. Caso o grafo esteja numerado de forma adequada os algoritmos são ótimos e são executados em tempo paralelo O(log n) com m/log n processadores.