Finding strongly connected components in distributed graphs

William McLendon; Bruce Hendrickson; Steven J. Plimpton; Lawrence Rauchwerger

doi:10.1016/j.jpdc.2005.03.007

Finding strongly connected components in distributed graphs

William McLendon, Bruce Hendrickson, Steven J. Plimpton, Lawrence Rauchwerger

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

Abstract

The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.

Original language	English (US)
Pages (from-to)	901-910
Number of pages	10
Journal	Journal of Parallel and Distributed Computing
Volume	65
Issue number	8
DOIs	https://doi.org/10.1016/j.jpdc.2005.03.007
State	Published - Aug 2005
Externally published	Yes

Keywords

Graph algorithm
Parallel computing
Strongly connected components

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Online availability

10.1016/j.jpdc.2005.03.007

Library availability

Discover UIUC Full Text

Cite this

@article{c2ef1f433416422a94ab8298fdb20355,

title = "Finding strongly connected components in distributed graphs",

abstract = "The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.",

keywords = "Graph algorithm, Parallel computing, Strongly connected components",

author = "William McLendon and Bruce Hendrickson and Plimpton, {Steven J.} and Lawrence Rauchwerger",

note = "Funding Information: This work was performed at Sand ia National Laboratories, a multiprogram laboratory operated by Sand ia Corporation, a Lockheed-Martin Company, for the US DOE under Contract Number DE-AC-94AL85000. The work has been sponsored by DOE{\textquoteright}s ASCI program. The authors would also like to thank Marvin Adams, Nancy Amato, Shawn, Pautz and Ali Pinar for their contributions to this work.",

year = "2005",

month = aug,

doi = "10.1016/j.jpdc.2005.03.007",

language = "English (US)",

volume = "65",

pages = "901--910",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "8",

}

TY - JOUR

T1 - Finding strongly connected components in distributed graphs

AU - McLendon, William

AU - Hendrickson, Bruce

AU - Plimpton, Steven J.

AU - Rauchwerger, Lawrence

N1 - Funding Information: This work was performed at Sand ia National Laboratories, a multiprogram laboratory operated by Sand ia Corporation, a Lockheed-Martin Company, for the US DOE under Contract Number DE-AC-94AL85000. The work has been sponsored by DOE’s ASCI program. The authors would also like to thank Marvin Adams, Nancy Amato, Shawn, Pautz and Ali Pinar for their contributions to this work.

PY - 2005/8

Y1 - 2005/8

N2 - The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.

AB - The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver.

KW - Graph algorithm

KW - Parallel computing

KW - Strongly connected components

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

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

U2 - 10.1016/j.jpdc.2005.03.007

DO - 10.1016/j.jpdc.2005.03.007

M3 - Article

AN - SCOPUS:20444476140

VL - 65

SP - 901

EP - 910

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 8

ER -

Finding strongly connected components in distributed graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this