A parallel algorithm for finding spanning trees of graphs
| dc.citation.issue | 1690 | pt_BR |
| dc.creator | Szwarcfiter, Jayme Luiz | |
| dc.date.accessioned | 2016-12-06T17:03:05Z | |
| dc.date.available | 2026-05-16T03:03:46Z | |
| dc.date.issued | 1990-06-30 | |
| dc.description.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. | en |
| dc.description.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. | pt_BR |
| dc.embargo.terms | aberto | pt_BR |
| dc.identifier.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) | pt_BR |
| dc.identifier.uri | http://hdl.handle.net/11422/1139 | |
| dc.language | eng | pt_BR |
| dc.publisher.country | Brasil | pt_BR |
| dc.publisher.department | Instituto TƩrcio Pacitti de AplicaƧƵes e Pesquisas Computacionais | pt_BR |
| dc.relation.ispartof | RelatĆ³rio TĆ©cnico NCE | pt_BR |
| dc.rights | Acesso Aberto | pt_BR |
| dc.subject | Algorithms | en |
| dc.subject | Graphs | en |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
| dc.title | A parallel algorithm for finding spanning trees of graphs | pt_BR |
| dc.type | RelatĆ³rio | pt_BR |