Finding strongly connected components in distributed graphs

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

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)901-910
Number of pages10
JournalJournal of Parallel and Distributed Computing
Volume65
Issue number8
DOIs
StatePublished - Aug 2005

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

Fingerprint Dive into the research topics of 'Finding strongly connected components in distributed graphs'. Together they form a unique fingerprint.

  • Cite this