Relatório
A parallel algorithm for finding spanning trees of graphs
Registro en:
SZWARCFITER, J. L. A parallel algorithm for finding spanning trees of graphs. Rio de Janeiro: NCE, UFRJ, 1990. 10 p. (Relatório Técnico, 16/90)
Autor
Szwarcfiter, Jayme Luiz
Institución
Resumen
We describe a parallel algorihm for finding the connected components of a graph. The algorithm constructs a spanning tree for each of its connected components in O(log²n) time with O((n+m)/log n) processors and O(n+m) space, under a CREW PRAM model, where n and m are the number of vertices and edges of the graph, respectively. Descrevemos um algoritmo paralelo para determinar os componentes conexos de uma grafo. O algoritmo constroi uma árvore geradora para cada um de seus componentes conexos em tempo O(log² n), com O((n+m)/log n) processadores e O(n+m) espaço, sob um modelo CREW PRAM, onde n e m representam os
números de vertices e arestas do grafo, respectivamente.