Improved Distributed Algorithms for SCC Decomposition

Jiri Barnat, Jakub Chaloupka, Jan Cornelis van de Pol

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    7 Citations (Scopus)

    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 languageUndefined
    Title of host publicationProceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation
    EditorsI. Cerna, Boudewijn R.H.M. Haverkort
    Place of PublicationAmsterdam
    PublisherElsevier
    Pages63-77
    Number of pages15
    DOIs
    Publication statusPublished - 4 Mar 2008
    Event6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007 - Berlin, Germany
    Duration: 8 Jul 20078 Jul 2007
    Conference number: 6
    http://anna.fi.muni.cz/PDMC/PDMC07/

    Publication series

    NameElectronic Notes in Theoretical Computer Science
    PublisherElsevier
    Number1
    Volume198
    ISSN (Print)1571-0661
    ISSN (Electronic)1571-0661

    Workshop

    Workshop6th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2007
    Abbreviated titlePDMC
    CountryGermany
    CityBerlin
    Period8/07/078/07/07
    Internet address

    Keywords

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

    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). [10.1016/j.entcs.2008.02.001] (Electronic Notes in Theoretical Computer Science; Vol. 198, No. 1). Amsterdam: Elsevier. https://doi.org/10.1016/j.entcs.2008.02.001
    Barnat, Jiri ; Chaloupka, Jakub ; van de Pol, Jan Cornelis. / Improved Distributed Algorithms for SCC Decomposition. Proceedings of the 6th International Workshop on Parallel and Distributed Methods in verifiCation. editor / I. Cerna ; Boudewijn R.H.M. Haverkort. Amsterdam : Elsevier, 2008. pp. 63-77 (Electronic Notes in Theoretical Computer Science; 1).
    @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",
    year = "2008",
    month = "3",
    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",

    }

    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 proceedingConference contributionAcademicpeer-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 -

    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). https://doi.org/10.1016/j.entcs.2008.02.001