Name
Title | ||
|---|---|---|
On fast parallel detection of strongly connected components (SCC) in small-world graphs |
Abstract | ||
|---|---|---|
Detecting strongly connected components (SCCs) in a directed graph is a fundamental graph analysis algorithm that is used in many science and engineering domains. Traditional approaches in parallel SCC detection, however, show limited performance and poor scaling behavior when applied to large real-world graph instances. In this paper, we investigate the shortcomings of the conventional approach and propose a series of extensions that consider the fundamental properties of real-world graphs, e.g. the small-world property. Our scalable implementation offers excellent performance on diverse, small-world graphs resulting in a 5.01× to 29.41× parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2503210.2503246 | SC |
Keywords | Field | DocType |
strongly connected component detection,fundamental property,limited performance,large real-world graph instances,small-world graph,fundamental graph analysis algorithm,optimal sequential algorithm,strongly connected components (scc),real-world graph,excellent performance,graph algorithms,parallel algorithms,fast parallel detection,large real-world graph instance,directed graph,small-world graphs,parallel speedup,multicore,small-world property,directed graphs,parallel scc detection | Block graph,Modular decomposition,Computer science,Parallel computing,Directed graph,Implicit graph,Theoretical computer science,Graph product,Pathwidth,Strongly connected component,Graph (abstract data type),Distributed computing | Conference |
ISSN | ISBN | Citations |
2167-4329 | 978-1-4503-2378-9 | 33 |
PageRank | References | Authors |
1.00 | 22 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sungpack Hong | 1 | 864 | 33.20 |
| Nicole C. Rodia | 2 | 33 | 1.00 |
| Kunle Olukotun | 3 | 4532 | 373.50 |