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, vol. 2008, 198(1), p. 63-77. ISSN 1571-0661. 2008.

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

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• 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

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.

Abstract (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