2013/10/30 by Sungpack Hong, Nicole C. Rodia, Kunle Olukotun · 92 citations
Physics and Astronomy · Computer Science · Mathematics · #Complex Network Analysis Techniques #Network Packet Processing and Optimization #Graph theory and applications #Computer science #Scalability #Speedup #Parallel computing #Scaling #Connected component #Graph #Theoretical computer science #Modular decomposition #Pathwidth #Line graph #Mathematics #Artificial intelligence
paper · doi:10.1145/2503210.2503246
openalex publication_date 2013/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.01x to 29.41x parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads.