Improved Distributed Algorithms for SCC Decomposition

We study and improve the OBF technique, which was used in distributed algorithms for the decomposi- tion 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 check- ing applications. The experimental results are compared with that of other successful SCC decomposition techniques