Distributed Algorithms for SCC Decomposition
Open Access
- 1 February 2009
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- Vol. 21 (1), 23-44
- https://doi.org/10.1093/logcom/exp003
Abstract
We study existing parallel algorithms for the decomposition of a partitioned graph into its strongly connected components (SCCs). In particular, we identify several individual procedures that the algorithms are assembled from and show how to assemble a new and more efficient algorithm, called Recursive OBF (OBFR), to solve the decomposition problem. We also report on a thorough experimental study to evaluate the new algorithm. It shows that it is possible to perform SCC decomposition in parallel efficiently and that OBFR, if properly implemented, is the best choice in most cases.Keywords
This publication has 6 references indexed in Scilit:
- Finding strongly connected components in distributed graphsJournal of Parallel and Distributed Computing, 2005
- Improved processor bounds for parallel algorithms for weighted directed graphsInformation Processing Letters, 1993
- Faster optimal parallel prefix sums and list rankingInformation and Computation, 1989
- An improved parallel algorithm that computes the BFS numbering of a directed graphInformation Processing Letters, 1988
- Depth-first search is inherently sequentialInformation Processing Letters, 1985
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972