SCCMulti: An improved parallel strongly connected components algorithm

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

doi:10.1145/2555243.2555286

SCCMulti: An improved parallel strongly connected components algorithm

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	393-394
Number of pages	2
Journal	ACM SIGPLAN Notices
Volume	49
Issue number	8
DOIs	https://doi.org/10.1145/2555243.2555286
State	Published - Aug 2014
Externally published	Yes

Keywords

Parallel Graph Algorithms
Randomized Algorithms
Strongly Connected Components

ASJC Scopus subject areas

General Computer Science

Online availability

10.1145/2555243.2555286

Library availability

Discover UIUC Full Text

Cite this

@article{e2a05945869f455e9db3f591fe38489d,

title = "SCCMulti: An improved parallel strongly connected components algorithm",

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.",

keywords = "Parallel Graph Algorithms, Randomized Algorithms, Strongly Connected Components",

author = "Daniel Tomkins and Timmie Smith and Amato, {Nancy M.} and Lawrence Rauchwerger",

year = "2014",

month = aug,

doi = "10.1145/2555243.2555286",

language = "English (US)",

volume = "49",

pages = "393--394",

journal = "ACM SIGPLAN Notices",

issn = "1523-2867",

publisher = "Association for Computing Machinery",

number = "8",

}

TY - JOUR

T1 - SCCMulti

T2 - An improved parallel strongly connected components algorithm

AU - Tomkins, Daniel

AU - Smith, Timmie

AU - Amato, Nancy M.

AU - Rauchwerger, Lawrence

PY - 2014/8

Y1 - 2014/8

N2 - 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.

AB - 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.

KW - Parallel Graph Algorithms

KW - Randomized Algorithms

KW - Strongly Connected Components

UR - http://www.scopus.com/inward/record.url?scp=84950133441&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950133441&partnerID=8YFLogxK

U2 - 10.1145/2555243.2555286

DO - 10.1145/2555243.2555286

M3 - Article

AN - SCOPUS:84950133441

SN - 1523-2867

VL - 49

SP - 393

EP - 394

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

IS - 8

ER -

SCCMulti: An improved parallel strongly connected components algorithm

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this