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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.jpdc.2005.03.007 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
strongly connected components,parallel computing | Modular decomposition,Parallel algorithm,Computer science,Path-based strong component algorithm,Parallel computing,Directed graph,Kosaraju's algorithm,Theoretical computer science,Connected component,Tarjan's strongly connected components algorithm,Strongly connected component,Distributed computing | Journal |
Volume | Issue | ISSN |
65 | 8 | 0743-7315 |
Citations | PageRank | References |
39 | 1.62 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
William Mclendon | 1 | 176 | 13.59 |
Bruce Hendrickson | 2 | 1669 | 214.08 |
Steven J. Plimpton | 3 | 264 | 22.82 |
Lawrence Rauchwerger | 4 | 1458 | 101.57 |