Improved Distributed Algorithms for SCC Decomposition

Jiri Barnat; Jakub Chaloupka; Jan Cornelis van de Pol

doi:10.1016/j.entcs.2008.02.001

Improved Distributed Algorithms for SCC Decomposition

Jiri Barnat
, Jakub Chaloupka
, Jan Cornelis van de Pol

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 Citations (Scopus)

1 Downloads (Pure)

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	https://doi.org/10.1016/j.entcs.2008.02.001
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	http://anna.fi.muni.cz/PDMC/PDMC07/

Keywords

FMT-TOOLS
FMT-MC: MODEL CHECKING
IR-62248
METIS-250956
EWI-12287

Access to Document

10.1016/j.entcs.2008.02.001

http://eprints.eemcs.utwente.nl/secure2/12287/01/sccs.pdf

Cite this

Barnat, J., Chaloupka, J., & van de Pol, J. C. (2008). Improved Distributed Algorithms for SCC Decomposition. In I. Cerna, & B. R. H. M. Haverkort (Eds.), Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation (pp. 63-77). Article 10.1016/j.entcs.2008.02.001 (Electronic Notes in Theoretical Computer Science; Vol. 198, No. 1). Elsevier. https://doi.org/10.1016/j.entcs.2008.02.001

@inproceedings{33b4b714e32a4d2093ad71a672ec5e38,

title = "Improved Distributed Algorithms for SCC Decomposition",

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.",

keywords = "FMT-TOOLS, FMT-MC: MODEL CHECKING, IR-62248, METIS-250956, EWI-12287",

author = "Jiri Barnat and Jakub Chaloupka and \{van de Pol\}, \{Jan Cornelis\}",

note = "10.1016/j.entcs.2008.02.001 ; 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007 ; Conference date: 08-07-2007 Through 08-07-2007",

year = "2008",

month = mar,

day = "4",

doi = "10.1016/j.entcs.2008.02.001",

language = "Undefined",

series = "Electronic Notes in Theoretical Computer Science",

publisher = "Elsevier",

number = "1",

pages = "63--77",

editor = "I. Cerna and Haverkort, \{Boudewijn R.H.M.\}",

booktitle = "Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation",

url = "http://anna.fi.muni.cz/PDMC/PDMC07/",

}

Barnat, J, Chaloupka, J & van de Pol, JC 2008, Improved Distributed Algorithms for SCC Decomposition. in I Cerna & BRHM Haverkort (eds), Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation., 10.1016/j.entcs.2008.02.001, Electronic Notes in Theoretical Computer Science, no. 1, vol. 198, Elsevier, Amsterdam, pp. 63-77, 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007, Berlin, Germany, 8/07/07. https://doi.org/10.1016/j.entcs.2008.02.001

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 - Conference code: 6

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

T2 - 6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007

Y2 - 8 July 2007 through 8 July 2007

ER -

Barnat J, Chaloupka J, van de Pol JC. Improved Distributed Algorithms for SCC Decomposition. In Cerna I, Haverkort BRHM, editors, Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation. Amsterdam: Elsevier. 2008. p. 63-77. 10.1016/j.entcs.2008.02.001. (Electronic Notes in Theoretical Computer Science; 1). doi: 10.1016/j.entcs.2008.02.001