Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
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 |
| Unidade produtora: | 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) |
| Aparece nas coleções: | Relatórios |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 16_90_000040383.pdf | 2.6 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.