Distributed Algorithms for SCC Decomposition

Warning

This publication doesn't include Institute of Computer Science. 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:	Techniques for automatic verification and validation of software nad hardware systems Highly Parallel and Distributed Computing Systems Verification and Analysis of Large-Scale Computer Systems