Distributed Algorithms for SCC Decomposition

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

doi:10.1093/logcom/exp003

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

28 Citations (Scopus)

485 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 language	Undefined
Article number	10.1093/logcom/exp003
Pages (from-to)	23-44
Number of pages	22
Journal	Journal of logic and computation
Volume	Advance Ac
Issue number	1
DOIs	https://doi.org/10.1093/logcom/exp003
Publication status	Published - 17 Feb 2009

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{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 = feb,

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",

}

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

SN - 0955-792X

VL - Advance Ac

SP - 23

EP - 44

JO - Journal of logic and computation

JF - Journal of logic and computation

IS - 1

M1 - 10.1093/logcom/exp003

ER -