Improved Distributed Algorithms for SCC Decomposition

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. 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 2008
Type Article in Periodical
Magazine / Source Electronic Notes in Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords SCC decomposition; parallel; distributed; OBF
Description We study and improve the OBF technique, which was used in distributed algorithms for the decomposition of a partitioned graph into its strongly connected components. In particular, we introduce a recursive variant of OBF and experimentally evaluate several different implementations of it that vary in the degree of parallelism. For the evaluation we used synthetic graphs with a few large components and graphs with many small components. We also experimented with graphs that arise as state spaces in real model checking applications. The experimental results are compared with that of other successful SCC decomposition techniques.
Related projects:

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