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

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

  • Author(s): Coppersmith, Don
  • Fleischer, Lisa
  • Hendrickson, Bruce
  • Pinar, Ali
  • et al.
Abstract

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
Current View