Distributed Algorithms for SCC Decomposition

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ří CHALOUPKA Jakub VAN DE POL Jaco

Year of publication 2011
Type Article in Periodical
Magazine / Source Journal of Logic and Computation
MU Faculty or unit

Faculty of Informatics

Citation
Web http://logcom.oxfordjournals.org/content/early/2009/02/17/logcom.exp003
Doi http://dx.doi.org/10.1093/logcom/exp003
Field Informatics
Keywords parallel algorithms; strongly connected components
Description We study existing parallel algorithms for the decomposition of a partitioned graph into its strongly connected components (SCCs). In particular, we identify several individual procedures that the algorithms are assembled from and show how to assemble a new and more efficient algorithm, called Recursive OBF (OBFR), to solve the decomposition problem. We also report on a thorough experimental study to evaluate the new algorithm. It shows that it is possible to perform SCC decomposition in parallel efficiently and that OBFR, if properly implemented, is the best choice in most cases.
Related projects:

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