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