Improved Distributed Algorithms for SCC Decomposition

BARNAT, Jiří, Jakub CHALOUPKA and Jaco VAN DE POL. Improved Distributed Algorithms for SCC Decomposition. Electronic Notes in Theoretical Computer Science. Elsevier, 2008, vol. 2008, 198(1), p. 63-77. ISSN 1571-0661.

Basic information

Original name

Improved Distributed Algorithms for SCC Decomposition

Name in Czech

Vylepšené algoritmy pro distribuovanou dekompozici grafu na silně souvislé komponenty

Authors

BARNAT, Jiří (203 Czech Republic, guarantor), Jakub CHALOUPKA (203 Czech Republic) and Jaco VAN DE POL (528 Netherlands)

Edition

Electronic Notes in Theoretical Computer Science, Elsevier, 2008, 1571-0661

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14330/08:00024165

Organization unit

Faculty of Informatics

Keywords in English

SCC decomposition; parallel; distributed; OBF

Tags

distributed, OBF, parallel, SCC decomposition

Tags

International impact, Reviewed

---

Abstract

V originále

We study and improve the OBF technique, which was used in distributed algorithms for the decomposition of a partitioned graph into its strongly connected components. In particular, we introduce a recursive variant of OBF and experimentally evaluate several different implementations of it that vary in the degree of parallelism. For the evaluation we used synthetic graphs with a few large components and graphs with many small components. We also experimented with graphs that arise as state spaces in real model checking applications. The experimental results are compared with that of other successful SCC decomposition techniques.

In Czech

Článek popisuje vylepšení techniky OBF, která se používá pro paralelní a distribuovanou detekci silně souvislých komponent v grafu. Je představena rekurzivní varianta OBF a několik možných způsobů implementace. Nové přístupy jsou vyhodnoceny jak nad syntetickými grafy, tak i nad grafy reálných systémů. Naměřené hodnoty jsou porovnány s ostatními přístupy pro paralelní dekompozici grafu na silně souvislé komponenty.

---

Links

GA201/06/1338, research and development project	Name: Automatizovaná verifikace softwaru Investor: Czech Science Foundation, Automated software verification
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1ET408050503, research and development project	Name: Techniky automatické verifikace a validace softwarových a hardwarových systémů Investor: Academy of Sciences of the Czech Republic, Techniques for automatic verification and validation of software nad hardware systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science