BARNAT, Jiří, Jakub CHALOUPKA a Jaco VAN DE POL. Improved Distributed Algorithms for SCC Decomposition. Electronic Notes in Theoretical Computer Science, Elsevier, 2008, roč. 2008, 198(1), s. 63-77. ISSN 1571-0661.
Další formáty:   BibTeX LaTeX RIS
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ří (203 Česká republika, garant), Jakub CHALOUPKA (203 Česká republika) a Jaco VAN DE POL (528 Nizozemsko).
Vydání Electronic Notes in Theoretical Computer Science, Elsevier, 2008, 1571-0661.
Další údaje
Originální 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 distributed, OBF, parallel, SCC decomposition
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Jiří Barnat, Ph.D., učo 3496. Změněno: 6. 3. 2008 09:48.
Anotace
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.
Anotace č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 VaVNázev: Automatizovaná verifikace softwaru
Investor: Grantová agentura ČR, Standardní projekty
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1ET408050503, projekt VaVNázev: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Akademie věd ČR, Informační společnost (Národní program výzkumu)
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 25. 9. 2020 03:46