Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1139
Tipo: Relatório
Título: A parallel algorithm for finding spanning trees of graphs
Autor(es)/Inventor(es): Szwarcfiter, Jayme Luiz
Resumo: 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.
Resumo : 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.
Palavras-chave: Algoritmos
Algorithms
Graphs
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 1690
Data de publicação: 30-Jun-1990
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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)
URI: http://hdl.handle.net/11422/1139
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
16_90_000040383.pdf2,6 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.