Distributed Algorithms for SCC Decomposition

I. Cerna (Editor), Jiri Barnat, Jakub Chaloupka, Boudewijn R.H.M. Haverkort (Editor), Jan Cornelis van de Pol

    Research output: Contribution to journalArticleAcademicpeer-review

    17 Citations (Scopus)
    190 Downloads (Pure)

    Abstract

    We study existing parallel algorithms for the decomposition of a partitioned graph into its strongly connected components (SCCs). In particular, we identify several individual procedures that the algorithms are assembled from and show how to assemble a new and more efficient algorithm, called Recursive OBF (OBFR), to solve the decomposition problem. We also report on a thorough experimental study to evaluate the new algorithm. It shows that it is possible to perform SCC decomposition in parallel efficiently and that OBFR, if properly implemented, is the best choice in most cases.
    Original languageUndefined
    Article number10.1093/logcom/exp003
    Pages (from-to)23-44
    Number of pages22
    JournalJournal of logic and computation
    VolumeAdvance Ac
    Issue number1
    DOIs
    Publication statusPublished - 17 Feb 2009

    Keywords

    • FMT-MC: MODEL CHECKING
    • EC Grant Agreement nr.: FP6/043235
    • IR-67466
    • CR-I.1.2
    • METIS-263759
    • EWI-15157

    Cite this