Parallel Algorithms for Finding SCCs in Implicitly Given Graphs

Warning

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

Authors	BARNAT Jiří MORAVEC Pavel
Year of publication	2006
Type	Article in Proceedings
Conference	Proceedings of the 5th International Workshop on Proceedings of 5th International Workshop on Parallel and Distributed Methods in verifiCation (PDMC 2006)
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:	Integrated approach to education of PhD students in the area of parallel and distributed systems Techniques for automatic verification and validation of software nad hardware systems Institute for Theoretical Computer Science Highly Parallel and Distributed Computing Systems Automated software verification