Abstract
| 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 | 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
Cite this
}
Improved Distributed Algorithms for SCC Decomposition. / Barnat, Jiri; Chaloupka, Jakub; van de Pol, Jan Cornelis.
Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation. ed. / I. Cerna; Boudewijn R.H.M. Haverkort. Amsterdam : Elsevier, 2008. p. 63-77 10.1016/j.entcs.2008.02.001 (Electronic Notes in Theoretical Computer Science; Vol. 198, No. 1).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Improved Distributed Algorithms for SCC Decomposition
AU - Barnat, Jiri
AU - Chaloupka, Jakub
AU - van de Pol, Jan Cornelis
N1 - 10.1016/j.entcs.2008.02.001
PY - 2008/3/4
Y1 - 2008/3/4
N2 - 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.
AB - 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.
KW - FMT-TOOLS
KW - FMT-MC: MODEL CHECKING
KW - IR-62248
KW - METIS-250956
KW - EWI-12287
U2 - 10.1016/j.entcs.2008.02.001
DO - 10.1016/j.entcs.2008.02.001
M3 - Conference contribution
T3 - Electronic Notes in Theoretical Computer Science
SP - 63
EP - 77
BT - Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation
A2 - Cerna, I.
A2 - Haverkort, Boudewijn R.H.M.
PB - Elsevier
CY - Amsterdam
ER -