Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
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 |
| Production unit: | 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) |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 16_90_000040383.pdf | 2.6 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.