Improved Distributed Algorithms for SCC Decomposition

Barnat, Jiri and Chaloupka, Jakub and Pol van de, Jaco (2008) Improved Distributed Algorithms for SCC Decomposition. In: 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007, 8 July 2007, Berlin, Germany.

PDF
Restricted to UT campus only: Request a copy
335Kb

Abstract:	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.
Item Type:	Conference or Workshop Item
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Formal Methods and Tools (FMT)
Link to this item:	http://purl.utwente.nl/publications/62248
Official URL:	http://dx.doi.org/10.1016/j.entcs.2008.02.001
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 250956