Distributed Algorithms for SCC Decomposition

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

Research output: Contribution to journalArticleScientificpeer-review

16 Citations (Scopus)

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 languageEnglish
Pages (from-to)23-44
Number of pages22
JournalJournal for Logic and Computation
VolumeAdvance Ac
Issue number1
DOIs
Publication statusPublished - 17 Feb 2009
Externally publishedYes

Keywords

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

Fingerprint Dive into the research topics of 'Distributed Algorithms for SCC Decomposition'. Together they form a unique fingerprint.

  • Cite this