Abstract
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.
Original language | Undefined |
---|---|
Title of host publication | Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation |
Editors | I. Cerna, Boudewijn R.H.M. Haverkort |
Place of Publication | Amsterdam |
Publisher | Elsevier |
Pages | 63-77 |
Number of pages | 15 |
DOIs | |
Publication status | Published - 4 Mar 2008 |
Event | 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007 - Berlin, Germany Duration: 8 Jul 2007 → 8 Jul 2007 Conference number: 6 http://anna.fi.muni.cz/PDMC/PDMC07/ |
Publication series
Name | Electronic Notes in Theoretical Computer Science |
---|---|
Publisher | Elsevier |
Number | 1 |
Volume | 198 |
ISSN (Print) | 1571-0661 |
ISSN (Electronic) | 1571-0661 |
Workshop
Workshop | 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007 |
---|---|
Abbreviated title | PDMC |
Country/Territory | Germany |
City | Berlin |
Period | 8/07/07 → 8/07/07 |
Internet address |
Keywords
- FMT-TOOLS
- FMT-MC: MODEL CHECKING
- IR-62248
- METIS-250956
- EWI-12287