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 |
Externally published | Yes |
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