Finding strongly connected components in distributed graphs Academic Article uri icon


  • The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver. 2005 Elsevier Inc. All rights reserved.

published proceedings

  • Journal of Parallel and Distributed Computing

author list (cited authors)

  • McLendon III, W., Hendrickson, B., Plimpton, S. J., & Rauchwerger, L.

citation count

  • 56

complete list of authors

  • McLendon III, William||Hendrickson, Bruce||Plimpton, Steven J||Rauchwerger, Lawrence

publication date

  • August 2005