Finding strongly connected components in distributed graphs

abstract

• 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.

authors

• Rauchwerger, Lawrence

published proceedings

• JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

author list (cited authors)

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

citation count

• 59

complete list of authors

• McLendon, W||Hendrickson, B||Plimpton, SJ||Rauchwerger, L

publication date

• August 2005

publisher

• Elsevier  Publisher

published in

• Journal of Parallel and Distributed Computing  Journal

keywords

• Graph Algorithm
• Parallel Computing
• Strongly Connected Components

Digital Object Identifier (DOI)

• 10.1016/j.jpdc.2005.03.007

start page

• 901

end page

• 910

volume

• 65

issue

• 8

URL

• http://dx.doi.org/10.1016/j.jpdc.2005.03.007