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

16 Citations (Scopus)
145 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

Cerna, I. (Editor) ; Barnat, Jiri ; Chaloupka, Jakub ; Haverkort, Boudewijn R.H.M. (Editor) ; van de Pol, Jan Cornelis. / Distributed Algorithms for SCC Decomposition. In: Journal of logic and computation. 2009 ; Vol. Advance Ac, No. 1. pp. 23-44.
@article{91eabb5757384487a3042645ee698003,
title = "Distributed Algorithms for SCC Decomposition",
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.",
keywords = "FMT-MC: MODEL CHECKING, EC Grant Agreement nr.: FP6/043235, IR-67466, CR-I.1.2, METIS-263759, EWI-15157",
author = "I. Cerna and Jiri Barnat and Jakub Chaloupka and Haverkort, {Boudewijn R.H.M.} and {van de Pol}, {Jan Cornelis}",
note = "Advance Access since March 2009",
year = "2009",
month = "2",
day = "17",
doi = "10.1093/logcom/exp003",
language = "Undefined",
volume = "Advance Ac",
pages = "23--44",
journal = "Journal of logic and computation",
issn = "0955-792X",
publisher = "Oxford University Press",
number = "1",

}

Cerna, I (ed.), Barnat, J, Chaloupka, J, Haverkort, BRHM (ed.) & van de Pol, JC 2009, 'Distributed Algorithms for SCC Decomposition' Journal of logic and computation, vol. Advance Ac, no. 1, 10.1093/logcom/exp003, pp. 23-44. https://doi.org/10.1093/logcom/exp003

Distributed Algorithms for SCC Decomposition. / Cerna, I. (Editor); Barnat, Jiri; Chaloupka, Jakub; Haverkort, Boudewijn R.H.M. (Editor); van de Pol, Jan Cornelis.

In: Journal of logic and computation, Vol. Advance Ac, No. 1, 10.1093/logcom/exp003, 17.02.2009, p. 23-44.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Distributed Algorithms for SCC Decomposition

AU - Barnat, Jiri

AU - Chaloupka, Jakub

AU - van de Pol, Jan Cornelis

A2 - Cerna, I.

A2 - Haverkort, Boudewijn R.H.M.

N1 - Advance Access since March 2009

PY - 2009/2/17

Y1 - 2009/2/17

N2 - 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.

AB - 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.

KW - FMT-MC: MODEL CHECKING

KW - EC Grant Agreement nr.: FP6/043235

KW - IR-67466

KW - CR-I.1.2

KW - METIS-263759

KW - EWI-15157

U2 - 10.1093/logcom/exp003

DO - 10.1093/logcom/exp003

M3 - Article

VL - Advance Ac

SP - 23

EP - 44

JO - Journal of logic and computation

JF - Journal of logic and computation

SN - 0955-792X

IS - 1

M1 - 10.1093/logcom/exp003

ER -