Skip to main content
Open Access Publications from the University of California

A divide-and-conquer algorithm for identifying strongly connected components


Strongly connected components of a directed graph can be found in an optimal linear time, by algorithms based on depth first search. Unfortunately, depth first search is difficult to parallelize. We describe two divide--and--conquer algorithms for this problem that have significantly greater potential for parallelization. We show the expected serial runtime of our simpler algorithm to be $O(m\lg n)$, for a graph with $n$vertices and $m$ edges. We then show that the second algorithm has$O(m\lg n)$ worst--case complexity.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View