Distributed Algorithms for SCC Decomposition

Jiri Barnat; Jakub Chaloupka; Jan Cornelis van de Pol; I. Cerna; Boudewijn R.H.M. Haverkort

doi:10.1093/logcom/exp003

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 journal › Article › Scientific › peer-review

26 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 language	English
Pages (from-to)	23-44
Number of pages	22
Journal	Journal for Logic and Computation
Volume	Advance Ac
Issue number	1
DOIs	https://doi.org/10.1093/logcom/exp003
Publication status	Published - 17 Feb 2009
Externally published	Yes

Keywords

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

Access to Document

10.1093/logcom/exp003

Cite this

@article{c48b64a962664f24862383d5fda401c3,

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 = "Jiri Barnat and Jakub Chaloupka and {van de Pol}, {Jan Cornelis} and I. Cerna and Haverkort, {Boudewijn R.H.M.}",

note = "Advance Access since March 2009 M1 - 10.1093/logcom/exp003",

year = "2009",

month = feb,

day = "17",

doi = "10.1093/logcom/exp003",

language = "English",

volume = "Advance Ac",

pages = "23--44",

journal = "Journal for Logic and Computation",

issn = "0955-792X",

publisher = "Oxford University Press",

number = "1",

}

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 M1 - 10.1093/logcom/exp003

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

SN - 0955-792X

VL - Advance Ac

SP - 23

EP - 44

JO - Journal for Logic and Computation

JF - Journal for Logic and Computation

IS - 1

ER -

Distributed Algorithms for SCC Decomposition

Abstract

Keywords

Access to Document

Fingerprint

Cite this