Editing Strongly connected component (section)

===Reachability-based algorithms===

Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize.  Fleischer et al.<ref name="Fleischer">{{citation|doi=10.1007/3-540-45591-4_68|isbn=978-3-540-67442-9|chapter=On Identifying Strongly Connected Components in Parallel|title=Parallel and Distributed Processing|series=Lecture Notes in Computer Science|year=2000|last1=Fleischer|first1=Lisa K.|last2=Hendrickson|first2=Bruce|last3=Pınar|first3=Ali|volume=1800|pages=505–511|chapter-url=https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/irreg00.pdf}}</ref> in 2000 proposed a [[Divide and conquer algorithm|divide-and-conquer]] approach based on [[reachability]] queries, and such algorithms are usually called reachability-based SCC algorithms.  The idea of this approach is to pick a random pivot vertex and apply forward and backward reachability queries from this vertex.  The two queries partition the vertex set into 4 subsets: vertices reached by both, either one, or none of the searches.  One can show that a strongly connected component has to be contained in one of the subsets.  The vertex subset reached by both searches forms a strongly connected component, and the algorithm then recurses on the other 3 subsets.

The expected sequential running time of this algorithm is shown to be O(''n''&nbsp;log&thinsp;''n''), a factor of O(log&thinsp;''n'') more than the classic algorithms.  The parallelism comes from: (1) the reachability queries can be parallelized more easily (e.g. by a [[breadth-first search]] (BFS), and it can be fast if the [[diameter (graph theory)|diameter]] of the graph is small); and (2) the independence between the subtasks in the divide-and-conquer process.
This algorithm performs well on real-world graphs,<ref name="hong2013fast">{{citation|doi=10.1145/2503210.2503246|isbn=9781450323789|chapter=On fast parallel detection of strongly connected components (SCC) in small-world graphs|title=Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis - SC '13|year=2013|last1=Hong|first1=Sungpack|last2=Rodia|first2=Nicole C.|last3=Olukotun|first3=Kunle|pages=1–11|s2cid=2156324 |chapter-url=https://ppl.stanford.edu/papers/sc13-hong.pdf}}</ref> but does not have theoretical guarantee on the parallelism (consider if a graph has no edges, the algorithm requires O(''n'') levels of recursions).

Blelloch et al.<ref name="Parallel">{{citation|doi=10.1145/2935764.2935766|isbn=9781450342100|chapter=Parallelism in Randomized Incremental Algorithms|title=Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '16|year=2016|last1=Blelloch|first1=Guy E.|last2=Gu|first2=Yan|last3=Shun|first3=Julian|last4=Sun|first4=Yihan|pages=467–478|chapter-url=https://people.csail.mit.edu/guyan/paper/SPAA16/Incremental.pdf|doi-access=free|hdl=1721.1/146176|hdl-access=free}}.</ref> in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(''n''&nbsp;log&thinsp;''n'') still holds.  Furthermore, the queries then can be batched in a prefix-doubling manner (i.e. 1, 2, 4, 8 queries) and run simultaneously in one round.  The overall [[Analysis of parallel algorithms|span]] of this algorithm is log<sub>2</sub>&thinsp;''n'' reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.