Algortimos Paralelos para Árvores Geradoras e Componentes Conexos
Resumo
Dado um grafo G = (V, E) com n vértices em arestas, apresentamos uma implementação simples em uma CREW PRAM de algoritmos paralelos para computação da árvore geradora e dos componentes conexos de um grafo. Os algoritmos são executados em tempo paralelo O(log2n) com m/log n processadores. Caso o grafo esteja numerado de forma adequada os algoritmos são ótimos e são executados em tempo paralelo O(log n) com m/log n processadores.
Referências
B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Transactions on Computer, C-36:1258-1263, 1987.
E.N. Caceres, N. Deo, S. Sastry, and J.L. Szwarcfiter. Parallel algorithm for Euler tour. Technical report, University of Central Florida, 1990.
E.N. Cáceres, N. Deo, S. Sastry, and J.L. Szwarcfiter. On finding Euler tours. Parallel Proc. Letters, a ser publicado, 1992.
F.Y. Chin, J. Lam, and I. Chen. Efficient parallel algorithms for some graph problems. Communication of ACM, 25:659-665, 1982.
R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to optimal parallel list ranking. IEEE Annual Symposium on Foundations of Computer Science, pgs. 478-491, 1986.
D. Eppstein and Z. Galil. Parallel algorithmic techniques for combinatorial computation. Annals Review Computer Science, 3:233-283, 1988.
A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, 1988.
T. Hagerup and H. Shen. Improved nonconservative sequential and parallel integer sorting. Information Processing Letters, 36:57-63, 1990.
X. He. Efficient parallel algorithms for series parallel graphs. J. Algorithms, 12:409-430, 1991.
D.S. Hirschberg, A.K. Chandra, and D.V. Sarwate. Computing connected components on parallel computers. Communication of ACM, 22:461-464, 1979.
R.M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science- Vol. A, Capítulo 17, pgs. 869-941. The MIT Press/Elsevier, 1990.
C.P. Kruskal, L. Rudolph, and M. Snir. Efficient parallel algorithms for graph problems. Algorithmica, 5:43-64, 1990.
D. Nath and N. Maheshwari. Parallel algorithms for the connected components and minimal spanning tree problems. Information Processing Letters, 14:7-11, 1982.
Y. Shiloach and U. Vishkin. An o(log n) parallel connectivity algorithm. Journal of Algorithms, 3:57-63, 1982.
E.N. Caceres, N. Deo, S. Sastry, and J.L. Szwarcfiter. Parallel algorithm for Euler tour. Technical report, University of Central Florida, 1990.
E.N. Cáceres, N. Deo, S. Sastry, and J.L. Szwarcfiter. On finding Euler tours. Parallel Proc. Letters, a ser publicado, 1992.
F.Y. Chin, J. Lam, and I. Chen. Efficient parallel algorithms for some graph problems. Communication of ACM, 25:659-665, 1982.
R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to optimal parallel list ranking. IEEE Annual Symposium on Foundations of Computer Science, pgs. 478-491, 1986.
D. Eppstein and Z. Galil. Parallel algorithmic techniques for combinatorial computation. Annals Review Computer Science, 3:233-283, 1988.
A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, 1988.
T. Hagerup and H. Shen. Improved nonconservative sequential and parallel integer sorting. Information Processing Letters, 36:57-63, 1990.
X. He. Efficient parallel algorithms for series parallel graphs. J. Algorithms, 12:409-430, 1991.
D.S. Hirschberg, A.K. Chandra, and D.V. Sarwate. Computing connected components on parallel computers. Communication of ACM, 22:461-464, 1979.
R.M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science- Vol. A, Capítulo 17, pgs. 869-941. The MIT Press/Elsevier, 1990.
C.P. Kruskal, L. Rudolph, and M. Snir. Efficient parallel algorithms for graph problems. Algorithmica, 5:43-64, 1990.
D. Nath and N. Maheshwari. Parallel algorithms for the connected components and minimal spanning tree problems. Information Processing Letters, 14:7-11, 1982.
Y. Shiloach and U. Vishkin. An o(log n) parallel connectivity algorithm. Journal of Algorithms, 3:57-63, 1982.
Publicado
26/10/1992
Como Citar
CÁCERES, Edson Norberto.
Algortimos Paralelos para Árvores Geradoras e Componentes Conexos. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 4. , 1992, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1992
.
p. 413-426.
DOI: https://doi.org/10.5753/sbac-pad.1992.22725.
