SCCMulti: An improved parallel strongly connected components algorithm

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

Research output: Contribution to journalArticle

Abstract

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
Volume49
Issue number8
DOIs
StatePublished - Aug 2014

    Fingerprint

Keywords

  • Parallel Graph Algorithms
  • Randomized Algorithms
  • Strongly Connected Components

ASJC Scopus subject areas

  • Computer Science(all)

Cite this