Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
Open Access
- 1 August 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (3) , 580-599
- https://doi.org/10.1137/0213036
Abstract
The authors present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the O(lg**2n) time bound.published_or_final_versioKeywords
This publication has 10 references indexed in Scilit:
- Efficient parallel algorithms for some graph problemsCommunications of the ACM, 1982
- Parallel Algorithms in Graph Theory: Planarity TestingSIAM Journal on Computing, 1982
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- Fast, Efficient Parallel Algorithms for Some Graph ProblemsSIAM Journal on Computing, 1981
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Computing connected components on parallel computersCommunications of the ACM, 1979
- Parallel Computations in Graph TheorySIAM Journal on Computing, 1978
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973