Fast, Efficient Parallel Algorithms for Some Graph Problems
SIAM Journal on Computing1981Vol. 10(4), pp. 682–691
Citations Over TimeTop 10% of 1981 papers
Abstract
Algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity $O(\log ^2 n)$ are described for finding biconnected components, bridges, minimum spanning trees and fundamental cycles. In the algorithms for finding minimum spanning trees, bridges, and fundamental cycles, the number of processors used is small enough that the parallel algorithm is efficient in comparison with the best sequential algorithms for these problems. Several other algorithms are presented which are especially suitable for processing sparse graphs.
Related Papers
- → The Structure of Parallel Algorithms(1980)198 cited
- Fundamentals of sequential and parallel algorithms(1996)
- → Integrating parallel algorithm design with parallel machine models(1995)5 cited
- → Experiments with parallel algorithms for combinatorial problems(1988)6 cited
- Research on Parallel Algorithm and Related Problems(2008)