×

zbMATH — the first resource for mathematics

Finding strongly connected components in distributed graphs. (English) Zbl 1082.68086
Summary: 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.

MSC:
68R10 Graph theory (including graph drawing) in computer science
Software:
PMESC
PDF BibTeX XML Cite
Full Text: DOI