Parallel Algorithms for Finding SCCs in Implicitly Given Graphs

Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BARNAT Jiří MORAVEC Pavel

Year of publication 2007
Type Article in Proceedings
Conference Formal Methods: Applications and Technology
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords distributed verification; SCCs
Description We examine existing parallel algorithms for detection of strongly connected components and discuss their applicability to the case when the graph to be decomposed is given implicitly. In particular, we list individual techniques that parallel algorithms for SCC detection are assembled from and show how to assemble a new more efficient algorithm for solving the problem. In the paper we also report on a preliminary experimental study we did to evaluate the new algorithm.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.