J 2008

Improved Distributed Algorithms for SCC Decomposition

BARNAT, Jiří; Jakub CHALOUPKA a Jaco VAN DE POL

Základní údaje

Originální název

Improved Distributed Algorithms for SCC Decomposition

Název česky

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

Autoři

BARNAT, Jiří; Jakub CHALOUPKA a Jaco VAN DE POL

Vydání

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

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Kód RIV

RIV/00216224:14330/08:00024165

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

SCC decomposition; parallel; distributed; OBF

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 6. 3. 2008 09:48, prof. RNDr. Jiří Barnat, Ph.D.

Anotace

ORIG CZ

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.

Česky

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

Návaznosti

GA201/06/1338, projekt VaV
Název: Automatizovaná verifikace softwaru
Investor: Grantová agentura ČR, Automatizovaná verifikace softwaru
MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1ET408050503, projekt VaV
Název: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Akademie věd ČR, Techniky automatické verifikace a validace softwarových a hardwarových systémů
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky