SCCMulti: An improved parallel strongly connected components algorithm

Daniel Tomkins, Timmie Smith, Nancy M. Amato, Lawrence Rauchwerger

Research output: Contribution to journalArticlepeer-review


SCCMULTI is a new algorithm which eliminates the drawbacks of the previous algorithms and an experimental validation of SCCMULTI on a range of graphs. An experiment was conducted while implementing Divide-and-Conquer Strong Components (DCSC), MULTIPIVOT, and SCCMULTI using C++ and the STAPL library, a parallel library which provides a distributed graph. It was proved that SCCMULTI uses more pivots than DCSC, resulting in higher execution times on lower core counts.

Original languageEnglish (US)
Pages (from-to)393-394
Number of pages2
JournalACM SIGPLAN Notices
Issue number8
StatePublished - Aug 2014
Externally publishedYes


  • Parallel Graph Algorithms
  • Randomized Algorithms
  • Strongly Connected Components

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'SCCMulti: An improved parallel strongly connected components algorithm'. Together they form a unique fingerprint.

Cite this