Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1139
Type: Relatório
Title: A parallel algorithm for finding spanning trees of graphs
Author(s)/Inventor(s): Szwarcfiter, Jayme Luiz
Abstract: 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.
Abstract: 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.
Keywords: Algoritmos
Algorithms
Graphs
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 1690
Issue Date: 30-Jun-1990
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: 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
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
16_90_000040383.pdf2,6 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.