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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 901-910 |
| Number of pages | 10 |
| Journal | Journal of Parallel and Distributed Computing |
| Volume | 65 |
| Issue number | 8 |
| DOIs | |
| State | Published - Aug 2005 |
Keywords
- Graph algorithm
- Parallel computing
- Strongly connected components
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence
Fingerprint Dive into the research topics of 'Finding strongly connected components in distributed graphs'. Together they form a unique fingerprint.
Cite this
McLendon, W., Hendrickson, B., Plimpton, S. J., & Rauchwerger, L. (2005). Finding strongly connected components in distributed graphs. Journal of Parallel and Distributed Computing, 65(8), 901-910. https://doi.org/10.1016/j.jpdc.2005.03.007